SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Ian Hsieh; Soumya Snigdha Kundu; Tom Vercauteren; Reuben Dorent

cs.LGAug 28, 2026

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Authors: Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren, Reuben Dorent

Organizations: Sorbonne Université, Institut du Cerveau - Paris Brain Institute - ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, 75013 Paris, France · King’s College London, UK

Abstract

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(N^2)$ operations, which restricts its use on large-scale datasets (e.g. $N\geq10^4$ ). 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.

Figures & tables

Figure 1: Overview of the SinkSLOT pipeline. Inputs: two discrete measures

\mu

and

\nu

; the naïve dense coupling has

N\times M

nonzeros. Stage 1:

L

random directions are sampled and 1D OT problems are solved by sorting in

O(N\log N)

per slice; the resulting plans are aggregated into a sparse lifted plan

\mathbf{P}^{\mathrm{SOT}}

with at most

L(N+M-1)

nonzeros. Stage 2: a sparse Gibbs kernel

K_{\varepsilon}=\mathbf{P}^{\mathrm{SOT}}\odot\exp(-C/\varepsilon)

inherits this sparsity, reducing each log-domain Sinkhorn iteration from

O(NM)

O(L(N+M))

. Output: the sparse coupling

\mathbf{P}^{\star}_{\varepsilon}

and the SinkSLOT divergence

\mathrm{SLOT}_{\varepsilon}

, which requires no debiasing.

Method	Reference coupling	Reference coupling cost	Sinkhorn iter.
EOT ( Cuturi, 2013 )	$\mathbf{a}\otimes\mathbf{b}$	$O(N^{2})$	$O(N^{2})$
SROT ( Nguyen, 2026 )	$(1-\gamma)P^{\mathrm{SOT}}+\gamma\,\mathbf{a}\otimes\mathbf{b}$	$O(LNd+LN\log N+N^{2})$	$O(N^{2})$
SinkSLOT (ours)	$P^{\mathrm{SOT}}$	$O(LNd+LN\log N)$	$O(S)$

Table 1: Computational complexity of the reference coupling and each Sinkhorn iteration. Here,

S=|\mathcal{S}|\leq L(N+M-1)

denotes the number of nonzeros in the SOT plan, and we assume

N=M

for simplicity.

SinkSLOT speedup ( $\mathbf{\times}$ ):
	Half-moons			8-Gaussians			Two-rings			Gauss $d{=}3$			Gauss $d{=}64$
Cost gap threshold:	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$
FlashSinkhorn Ye et al. (2026)	13.1	8.4	8.4	17.5	19.4	16.7	36.4	14.7	8.2	4.3	9.7	9.6	2.8	6.7	11.4
SROT Nguyen (2026)	124.9	118.6	118.6	103.0	160.2	119.5	122.8	131.3	131.3	29.5	62.1	89.7	15.2	27.1	35.1
Spar-Sink Li et al. (2023)	4.8	2.5	2.5	—	—	37.4	45.5	5.5	3.3	—	—	—	—	—	—
Runtime (ms):

Table 2: SinkSLOT speedup over competing methods at each transport cost gap threshold. “—” indicates that the method did not reach the threshold at convergence (or after 10k Sinkhorn iterations).

N=10^{4}

d=2

unless otherwise specified. H100-80GB.

Figure 2: Forward-pass runtime against

(N,M)

and

d

. Error bars indicate the standard error over five random seeds.

Figure 3: Blob-to-crescent gradient flows. $N=M=1000$ . Regularisation strength $\varepsilon=0.01$ . $L=100$ slices. Performance is evaluated using the exact squared 2-Wasserstein distance $W_{2}^{2}$ ; bold indicates the lowest value at each intermediate step.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Visualisation of SinkSLOT transport plan for the three 2D datasets. Only

120

of the

10^{4}

points are shown for readability. Regularisation strength

\varepsilon=0.01

L=1024

slices.

Figure 5: Pareto fronts for the accuracy-speed trade-off on the four low-dimensional datasets. FlashSinkhorn vs SinkSLOT at three slice counts:

L=128

1024

, and

4096

N=M=10^{4}

Figure 6: Pareto fronts for the accuracy–speed trade-off on the Gaussian

d=64

dataset. FlashSinkhorn vs SinkSLOT at four slice counts.

Iterations of the fastest-time (speedup-table) run:
	Half-moons			8-Gaussians			Two-rings			Gauss $d{=}3$			Gauss $d{=}64$
Method	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$
SinkSLOT (ours)	420	140	140	3180	460	250	150	90	90	10000	3240	1430	430	520	990
FlashSink Ye et al. [2026]	260	70	70	3060	430	220	310	90	50	8220	4090	1920	430	430	430
SROT Nguyen [2026]	450	140	140	3210	470	260	150	100	100	7320	3290	1550	1230	870	700
Spar-Sink Li et al. [2023]	260	70	70	—	—	1010	654	96	50	—	—	—	—	—	—

Appendix

Table 3: Iterations run by the SAME configuration selected in the speedup table 2 (the fastest wall-clock run reaching each transport cost-gap threshold). “—” means no feasible run reached the threshold.

N=10^{4}

d=2

unless otherwise specified. H100-80GB.

	Half-moons			8-Gaussians			Two-rings			Gauss $d{=}3$			Gauss $d{=}64$
Method	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$	${\leq}1\%$	${\leq}5\%$	${\leq}10\%$
Peak memory (MB):
SinkSLOT (ours)	820	820	820	896	820	820	820	820	820	2580	1799	1281	5050	3007	1302
FlashSink Ye et al. [2026]	1785	1785	1785	1785	1785	1785	1785	1785	1785	1785	1785	1785	1806	1806	1806
SROT Nguyen [2026]	2359	2359	2359	2359	2359	2359	2359	2359	2359	2359	2359	2359	2380	2380	2380
SparSink Li et al. [2023]	1258	1258	1258	—	—	1258	1258	1258	1258	—	—	—	—	—	—

Appendix

Table 4: Lowest peak GPU memory (MB) among feasible runs reaching each transport gap threshold. “—” means no feasible run reached the threshold.

N=10^{4}

d=2

unless otherwise specified. H100-80GB.

Figure 7: Forward-pass peak memory against

(N,M)

and

d

. Error bars indicate the standard error over five random seeds.

step	analytic	FD (frozen)	rel. err.	$\|\Delta F\|/F$
0	$4.431\times 10^{-4}$	$4.431\times 10^{-4}$	$1.1\times 10^{-9}$	$1.6\times 10^{-6}$
10	$-2.906\times 10^{-4}$	$-2.906\times 10^{-4}$	$8.7\times 10^{-5}$	$1.3\times 10^{-5}$
25	$-6.904\times 10^{-5}$	$-6.903\times 10^{-5}$	$6.6\times 10^{-4}$	$8.6\times 10^{-5}$
40	$-7.862\times 10^{-6}$	$-7.853\times 10^{-6}$	$2.3\times 10^{-3}$	$3.2\times 10^{-4}$
50	$-6.683\times 10^{-6}$	$-6.696\times 10^{-6}$	$3.8\times 10^{-3}$	$1.8\times 10^{-4}$

Appendix

Table 5: Finite-difference check of term (I) along the flow,

\varepsilon=0.01

h=10^{-4}

, six random directions per point, float64 . “rel. err.” compares the analytic directional derivative to the central difference with

P^{\mathrm{SOT}}

frozen;

|\Delta F|/F

is the relative change in the value caused by rebuilding

P^{\mathrm{SOT}}

at the perturbed point, i.e. the only trace term (II) leaves.

Figure 8: Envelope gradient (I) and the solver residual along the blob-to-crescent flow, one column per

\varepsilon

N=M=1000

L=100

600

inner iterations. Top: term (I) computed analytically (closed form) and numerically (automatic differentiation with the prior coupling held constant), indistinguishable at this scale, together with the residual. Middle: the plan’s transport cost

\langle P,C\rangle

. Bottom: the exact

2

-Wasserstein distance

W_{2}

to the target. The residual is roughly constant while term (I) decays by two orders of magnitude, so it becomes comparable only after the transport cost has plateaued at its

\varepsilon

-dependent floor. ∗ marks a column whose solve is not converged at

600

iterations.

Optimal Transport

Optimal transport compares and transforms probability distributions by finding low-cost ways to move mass between them.

See all 284 papers

Sliced-Regularized Optimal Transport
Apr 27, 2026Khai NguyenOptimal Transport
The University of Texas at Austin
FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport
Oct 1, 2026Felix X. -F. Ye, Yu Chin Fabian Lim, Naigang Wang +1Optimal Transport GPU Kernel Optimization
Department of Mathematics & Statistics, University at Albany, Albany, NY, USA · IBM T. J. Watson Research Center, Yorktown Heights, NY, USA
Fast Log-Domain Sinkhorn Optimal Transport with Warp-Level GPU Reductions
Apr 4, 2026Hao XiaoOptimal Transport GPU Acceleration
ATLAS AI Lab

Apr 27, 2026J/K move · Enter open · S save

Sliced-Regularized Optimal Transport

Khai Nguyen

The University of Texas at Austin

Optimal Transport

Open paper AskPDF arXiv

We propose a new regularized optimal transport (OT) formulation, termed sliced-regularized optimal transport (SROT). Unlike entropic OT (EOT), which regularizes the transport plan toward an independent coupling, SROT regularizes it toward a smoothened sliced OT (SOT) plan. To the best of our knowledge, SROT is the first approach to leverage a version of SOT plan as a reference to improve classical OT. We provide a formal definition of SROT, derive its dual formulation, and provide a post-Bayesian interpretation of SROT. We then develop a Sinkhorn-style algorithm for efficient computation, retaining the same scalability advantages as EOT. By incorporating a scalable SOT plan as a prior, SROT yields more accurate approximations of the exact OT plan than EOT under the same level of regularization. Moreover, the resulting transport plan improves upon the reference SOT plan itself. We further introduce the corresponding OT divergence induced by SROT, named SROT divergence, and analyze its topological and computational properties. Finally, we validate our approach through experiments on synthetic datasets and color transfer tasks, demonstrating that SROT is better than both EOT and SOT in approximating exact OT. Additional experiments on gradient flows further highlight the advantages of SROT divergence.

Abstract

Optimal Transport

Explore similar work

Sliced-Regularized Optimal Transport

FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport

Fast Log-Domain Sinkhorn Optimal Transport with Warp-Level GPU Reductions