- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper presents FlashSinkhorn 2, a GPU solver for discrete entropic optimal transport with squared-Euclidean cost on low-dimensional point clouds. Its goal is to reach a prescribed marginal residual τ without evaluating all n×m point pairs at every Sinkhorn iteration.
FS2 sorts the points in Morton order and works in two stages:
Coarse stage. Nearby points are grouped into cells, and the problem is annealed on the cell centroids using FlashSinkhorn's streaming kernels. The resulting potentials are lifted to the points and accepted if a sampled marginal check passes. Fine stage. If the check fails, FS2 runs block-sparse Sinkhorn updates on the points. Block pairs are pruned by a bounding-box screen followed by exact verification. The pruning threshold depends on the block masses, and Theorem 1 bounds each omitted tile's contribution to every row and column. The kept tiles are executed with FlashSinkhorn's fused tensor-core kernel.
Response to rebuttal
Thank you for the response. The clarifications on W2 (post-hoc bound evaluation and sampled-check reliability) and W4 (block size B vs. peak memory) address my main concerns.
- I consider this a valuable contribution that makes entropic OT at the 10⁸-point scale practical on a single GPU.
- I recommend acceptance and have raised my rating to 4 and my confidence to 3.
Critical strengths
A sound core observation that pays off in practice. At moderate regularization, the entropic plan concentrates on nearby pairs, so most of the O(nm) work per Sinkhorn iteration is wasted. The paper exploits this in a way that holds up empirically: FS2 reaches the target residual on all 32 synthetic problems, where GeomLoss multiscale reaches it on 10. Where both succeed, FS2 is 74–645× faster. Every reported residual is evaluated on the returned potentials independently of the solver's own stopping check which makes the speed comparisons trustworthy. A demonstration at a new scale. Solving EOT between two 1.34×10⁸-particle measures on a single GPU, to a residual below 0.01 at a blur of one interparticle spacing, is a concrete capability. It matches the particle count that prior work on cosmological reconstruction treated with semi-discrete transport.
Critical weaknesses
- Novelty is mainly integrative
Coarse-to-fine annealing (GeomLoss), potential-based truncation and block relaxation (Schmitzer, 2019; L248–249) and the fused kernel (FlashSinkhorn) all come from prior work; the differences listed at L250–256 are implementation-level.
- The lift bound is not used in practice
By the authors' own statement, the bound of Proposition 1 exceeds τ on every problem (L215), so acceptance of a lift is always decided by a heuristic sampled check rather than by the theory.
- Narrow scope
FS2 is limited to squared-Euclidean cost in d ≤ 3 (L138–139), whereas most machine-learning uses of OT are high-dimensional, which limits its relevance to the ICLR audience.
- Very high memory cost
Peak memory is 8–10× that of the baselines (L400) and grows faster than n (40-fold for a 16-fold increase in n; L405–406), giving up the main advantage of streaming solvers.
Questions for authors
- Is the high memory cost inherent to the approach, or can it be reduced?
2 comments
Response to rebuttal
Thank you for the response. The clarifications on W2 (post-hoc bound evaluation and sampled-check reliability) and W4 (block size B vs. peak memory) address my main concerns.
- I consider this a valuable contribution that makes entropic OT at the 10⁸-point scale practical on a single GPU.
- I recommend acceptance and have raised my rating to 4 and my confidence to 3.
Response to imri
Thank you for your review.
W1 (novelty, see General Response, item 2). FS2's novelty is a GPU system that efficiently screens block pairs with a bound on the dropped mass. It adapts Schmitzer's truncation principle to the GPU, while GeomLoss uses a different mask. The implementation-level differences you note make this possible. In the 2²⁷ solve, for example, the tile index takes 2.9 GiB, where storing the same admitted pairs individually would take 11.7 TiB.
W2 (lift bound). Theorem 1 sets the block threshold of every sparse update. A post-hoc numerical evaluation of its residual bound is below τ for all 19 returns we evaluated, the 15 of Appendix E.4 and the four Quijote 2²⁴ returns in our answer to 8Dp5. It takes 9.8–39.1 s to compute at 2²⁴. Across 20 sampling seeds on each of the seven problems closest to τ, the sampled check never accepted a return above τ (Appendix E.4). Proposition 1's bound exceeds τ at our tolerances, so FS2 uses sampled residual checks to accept lifted potentials. Proposition 1 guides the coarse-to-fine transition: it separates the coarse marginal error, which further coarse updates shrink, from the centroid error, which no coarse update changes, so a rejected lift is followed by coarse updates until they stall.
W3 (scope). FS2 extends the scale of OT one GPU can solve. Its scope, squared-Euclidean costs in d ≤ 3, covers point clouds with 10⁵–10⁸ points per measure in computational biology, medical imaging and cosmology (Section 1). On one A100, FS2 solves EOT between two 1.34×10⁸-particle measures to a residual below 0.01 in under 2.5 hours, to our knowledge the largest discrete EOT problem solved to this accuracy within hours.
W4/Q1 (memory). FS2's additional peak memory is driven by its mask index, whose size depends on block size B. In the measured comparison, increasing B reduces memory with a small increase in runtime. Raising B from 128 to 256 cuts the peak 2.35× for 7% more time (NWJt W2/Q2). FS2 stores no kernel entries, and its mask index takes 24 bytes per tile. The 40-fold rise for a 16-fold rise in n occurs at fixed ε, where each point gains neighbors within the blur as n grows. On Quijote, the blur is fixed at one lattice spacing, and at τ = 0.05 the peak stays below the capacity of the 80 GiB GPU from 2²⁴ to 2²⁷ points.