acceptodds
Under review as a conference paper at ICLR 2027

FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport on GPU

17 views

Abstract

Streaming GPU solvers for entropic optimal transport (EOT), such as FlashSinkhorn, avoid storing the dense kernel but still evaluate all point pairs in every Sinkhorn iteration. We present **FlashSinkhorn 2** (FS2), a solver for squared-Euclidean cost on low-dimensional point clouds that solves large discrete EOT problems to a prescribed marginal residual on a single GPU by coupling two stages. A coarse stage solves on cell centroids, lifts the potentials to every point and, when a sampled marginal check rejects the lift, continues on the centroids, replacing most point-level updates. A block-sparse fine stage then removes the centroid error that coarse updates cannot. Its Morton-ordered blocks support screening and fused tensor-core execution, and a threshold set by the block masses bounds each omitted tile's contribution to every row and column. On synthetic benchmarks, FS2 reaches the target residual on all 32 problems and GeomLoss multiscale on 10. On one A100, FS2 solves discrete EOT between two -particle measures from a cosmological -body simulation, at an entropic blur equal to the mean interparticle distance, to an all-particle marginal residual below 0.01 in under 2.5 hours. To our knowledge, it is the largest discrete EOT problem solved to this accuracy within hours.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Entropic optimal transport, Sinkhorn algorithm, Block sparsity, GPU acceleration, Hardware software co-design

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_imriOpenReview ↗
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
  1. 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.

  1. 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.

  1. 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.

  1. 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
  1. Is the high memory cost inherent to the approach, or can it be reduced?
2 comments
AuthorsOpenReview ↗

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.

Reviewer_imriOpenReview ↗

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.
Reviewer_8Dp5OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents FlashSinkhorn 2, a GPU solver for entropic optimal transport with squared-Euclidean cost on point clouds in up to three dimensions. Building on FlashSinkhorn, it first solves a smaller problem using representative points and then refines the solution on the original points when needed. The refinement skips blocks of point pairs with small contributions, reducing the work performed by the existing GPU kernels. The paper also analyzes approximation errors and checks whether the returned solutions meet a target marginal residual.

Critical strengths

The paper provides a meaningful improvement in the scale of practical computation. Solving a problem with approximately 134 million points on each side using a single GPU is a substantial result. It addresses a clear limitation of FlashSinkhorn: avoiding storage of the full matrix still leaves a large amount of computation. Reducing this work makes the extension useful for the low-dimensional problems considered here.

It also presents useful ablations and careful checks of the reported accuracy. The paper examines the contributions of coarse computation and sparse refinement separately. For example, replacing sparse refinement with dense updates increases the solve time from about 4.17 to 33.33 seconds on one clustered problem. The synthetic results are checked using full marginal evaluations, and the largest simulation result receives additional precision checks. These experiments give concrete support to the practical contribution.

Critical weaknesses

The incremental benefit over existing methods needs broader evaluation at the same target accuracy. The reported 74–645x speedups over default GeomLoss occur on problems where FlashSinkhorn 2 needs no sparse refinement, and matching coarse cell counts reduces one advantage from about 212x to 1.4x. Tables 1b and 8 provide useful controlled comparisons, including about a 27x advantage on a problem requiring refinement, but cover few settings. The direct FlashSinkhorn comparison in Table 1a also ends at different residuals. Extending these comparisons would clarify how broadly the gains apply.

The reliability of default settings at large scale remains less established than the successful runs suggest. The largest simulation required manual configuration changes (Appendix F.2), and the solver stops on sampled checks, with fuller validation performed afterwards. The independent validation and sparse residual certificates support the reported solutions, so I do not regard these limitations as evidence of incorrect results. However, the reliability of automatic settings on new large-scale problems and the total runtime including certificate verification are not systematically evaluated. A small comparison of automatic and manual settings would help address this gap.

Questions for authors
  1. Could you extend the comparisons in Tables 7–8 to a few more representative problems, including cases that require sparse refinement, and report the time needed by each solver to meet the same marginal-residual tolerance? Comparing suitably configured GeomLoss and dense FlashSinkhorn on manageable problem sizes, together with the dense-refinement ablation, would help clarify the contribution beyond the existing methods.

  2. Could you add a small robustness experiment comparing the automatic settings with the manually selected settings across several problem sizes or accuracy targets? Please report independently evaluated final residuals and the total runtime including certificate verification, with the verification cost listed separately.

2 comments
AuthorsOpenReview ↗

Response to 8Dp5

Thank you for your review and for the questions about the 27× comparison and automatic settings.

W1/Q1 (broader comparisons, see General Response, item 1). The following comparisons address your questions. The solver comparisons use the same marginal-residual target, while the ablation fixes the number of fine updates:

  • GeomLoss, offline-tuned at approximately FS2's source-cell count on eight problems that extend Tables 7–8: automatic FS2 is faster on six, by 1.35–2.28×, including C, 2²⁰, ε = 0.001, where FS2 performs 15 fine updates, and offline-tuned FS2 is faster on seven of eight. Table 8's 27× was against GeomLoss at its default cells, offline-tuned to meet τ. On that problem, C, 2²¹, ε = 0.001, offline-tuned GeomLoss beats offline-tuned FS2, 8.797 s against 13.309 s in the same run.
  • Dense FlashSinkhorn, offline-tuned to the same tolerance, where Table 1a compared different residuals: on C, 2²⁰, ε = 0.001, it takes 285× automatic FS2's time, 1201.8 s against 4.212 s.
  • Dense-refinement ablation on the same problem: with the same 13 ordinary updates and two terminal previews, the sparse solve takes 4.165 s versus 33.327 s with dense refinement, an 8.00× speedup (Table 2).

W2/Q2 (automatic versus manual settings). On Quijote 2²⁴, we compare B/t selection at two tolerances using the same historical controller, with only the selector changed (Appendix F.6). Automatic selection meets both accuracy targets and is 2.1–2.6× faster than the manual settings, guarantee included. R is the independently evaluated full residual.

τSettingSolve (s)Guarantee (s)Total (s)R
0.05Manual146.7839.08185.860.04663
0.05Automatic60.979.7870.750.04282
0.01Manual731.7239.08770.800.009433
0.01Automatic348.839.82358.650.009439

Total sums the separately measured median solve and guarantee times; the independent full residual is excluded. Theorem 1's residual bound, listed separately as you asked, is below τ in all four cases and costs under 2% of an independent full residual evaluation, which takes about 2125 s per pair. At 2²⁷, outside the selector's supported range, we set t = 45 by hand, with the selector's B = 256 (Appendix F.2).

Thanks for the authors' responses, I think weak accept is enough for this paper.

Reviewer_GXFROpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces FlashSinkhorn 2 (FS2), an EOT solver that couples coarse Sinkhorn solves, dual potential lifting, and dynamic block-sparse fine updates accelerated by Flash-style streaming GPU kernels and sampled marginal checks, successfully scaling discrete EOT on 3D synthetic point clouds and cosmological data to over 10810^8 particles on a single A100 GPU.

Critical strengths
  1. Integrates prior multiscale and sparse OT techniques (Schmitzer, GeomLoss) into a efficient GPU-tailored low-dim EOT solver.
  2. Exceptional empirical scale, successfully solving instances with over 10810^8 particles.
Critical weaknesses
  1. Primarily system integration:The paper reads largely like an engineering synthesis and modular upgrade over Schmitzer[1] and GeomLoss[2]:
    • Streaming on-chip recomputation is an established technique.
    • Mass-dependent threshold: Under the main benchmark setup (uniform weights and fixed block size BB), the threshold \rho_{IJ} degenerates into a uniform constant. Consequently, the empirical benefit of mass-based screening is not demonstrated in the primary experiments.
    • Block-level screening: Block-level truncation and its GPU execution have direct precedent in GeomLoss[2], while dynamic support updates and conservative distance bounding already appear in Schmitzer[1]. FS2 mainly changes how screening is organized and executed; the paper should better isolate the distinct contribution and performance gain of these engineering choices.
  2. Insufficient baselines: The empirical comparison lacks an important baseline: a FlashSinkhorn with minibatch OT (MB-FS). Evaluating FS2 relative to simple minibatch partitioning across K∈{32,64,128,256,512}K \in \{32, 64, 128, 256, 512\} batches per cloud is necessary to demonstrate FS2's actual advantage. The paper’s evaluation setting (moderate-to-loose tolerances \tau \approx 10^{-2} paired with stopping based solely on marginal residuals) is exceptionally well-suited for minibatch approximations. Indeed, in my preliminary million-scale experiments, MB-FS appears quite competitive in runtime, marginal residual and rounded objective with FS2.

The scale of the experiment is commendable. If these concerns are fully addressed, I am willing to raise the score.

Questions for authors
  1. On the heterogeneous instance with n=m=2^{21} and ε=0.01 in Table 7, matching GeomLoss's coarse cell count to FS2's reduces the runtime ratio from approximately 212× to 1.4×. Furthermore, in several benchmark instances, FS2 meets the target residual immediately after the initial coarse lift without requiring any fine updates. Consequently, it is unclear how much of the reported speedup stems from well-chosen coarse resolutions under the currently loose tolerance (τ=0.005\tau = 0.005), rather than the newly proposed block-sparse fine stage. Could the authors clarify this by:
    • Evaluating GeomLoss with matched coarse scales and residual-based stopping criteria across more benchmark instances?
    • Providing a tolerance sweep to verify whether FS2’s performance advantage persists under higher-precision regimes (e.g., τ∈{10−4,10−6}\tau \in \{10^{-4}, 10^{-6}\})?
  2. For instances where the coarse stage dominates runtime, could introducing deeper recursive levels yield further speedups? Given that multi-level hierarchies are standard in existing multiscale OT methods [1,3,4], what is the rationale for restricting FS2 to a strictly two-level architecture?

[1] Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems

[2] Geometric Data Analysis, Beyond Convolutions

[3] A Sparse Multi-Scale Algorithm for Dense Optimal Transport

[4] A Memory-Efficient Hierarchical Algorithm for Large-Scale Optimal Transport Problems

1 comment
AuthorsOpenReview ↗

Response to GXFR

Thank you for your review. The revision adds the three experiments you asked for: the MB-FS baseline, GeomLoss at matched resolution, and the tolerance sweep.

W1 (system integration, see General Response, item 2). FS2's distinct contribution is a system of NVIDIA GPU kernels that efficiently screens block pairs and performs sparse updates with a bound on the dropped mass, a systems contribution in ICLR's infrastructure, software libraries, hardware and systems area. General Response, item 2, compares the design and measured gains against Schmitzer and GeomLoss. Streaming on-chip recomputation comes from FlashSinkhorn, and FS2 applies it to bounded block-sparse screening. With unequal block masses, the mass-dependent threshold preserves the bound while admitting up to 5.3% fewer tiles than a rule using the largest block mass, and the solve runs up to 3.3% faster (Appendix C.3). With uniform weights and B dividing n = m, it reduces to log(τ/4), as you note.

W2 (MB-FS baseline). We compare global EOT objectives (lower is better) after rounding both plans to their target marginals. We test one-round MB-FS at K = 32, 64, 128, 256, 512 on eight inputs (Appendix E.10).

  • One round. Split each measure into K equal-mass groups and pair each group once, so the plan covers K of K² group pairs and its objective includes ε log K. For each tested grouping and pairing, MB-FS's numerical lower bound applies even if all local problems are solved exactly. On the six inputs with an FS2 bound at τ = 0.005, even the lowest MB-FS lower bound exceeds FS2's feasible upper bound:
InputεFS2 upper boundLowest MB-FS lower bound
C, 2²⁰0.0010.054430.05577
C, 2²¹0.0010.054160.05567
C, 2²¹0.010.082190.11594
H, 2²⁰0.0010.004200.00796
H, 2²¹0.0010.004170.00766
H, 2²¹0.010.013930.04843

On C, 2²⁰, ε = 0.001, MB-FS takes 30.5–814.6 s including FP64 quality evaluation, versus FS2's solver-only 4.212 s. Ten of 40 one-round cases reach the update cap before meeting the local gap target.

  • All pairs. On C, 2²⁰, ε = 0.01, we pair every source group with every target group (K = 32). Each block's mass and local marginals are fixed. The resulting objective lies between FS2's at τ = 0.005 and 10⁻⁴:
PlanObjectiveFP64 boundTime (s)
FS2, τ = 0.0050.082282≤ 0.08243155.12
MB-FS, K = 32, all pairs0.081376≥ 0.0813731493.49
FS2, τ = 10⁻⁴0.081337≤ 0.081346112.93

All bounds are FP64 numerical bounds. FS2's applies to its rounded plan; MB-FS's to plans with its fixed group constraints. FS2's times are medians of three calls, including value bounds and 54.8 s for a feasible output. MB-FS takes 27.1× and 13.2× those times: one warmed call with 512 updates per block chosen offline, excluding the search and independent quality evaluation.

Q1 (matched resolution and tolerance sweep, see General Response, item 1). The 74–645× speedups over automatic GeomLoss come from FS2's coarse stage, since FS2 returns without fine updates on all ten of those problems. When the block-sparse fine stage performs updates, FS2 can also be faster, and running the same 13 ordinary updates and two terminal previews sparse instead of dense makes the solve 8.00× faster (Table 2).

  • Matched coarse scales. With GeomLoss offline-tuned at approximately FS2's source-cell count and meeting the same residual target on eight problems, automatic FS2 is faster on six, including C, 2²⁰, ε = 0.001, where it performs 15 fine updates, and offline-tuned FS2 on seven.
  • Tolerance sweep on C, 2²⁰, ε = 0.01, both solvers scored by the same FP64 evaluator. FS2 is faster than offline-tuned GeomLoss by 1.79× at τ = 0.005 and 1.89× at τ = 10⁻⁴, 58.13 s against 109.7 s. At τ = 10⁻⁶, an experimental full-support continuation from an extended 1024-update FS2 run reaches R = 7.57×10⁻⁷. Default FS2 does not meet this target; FP64 GeomLoss reaches R = 2.09×10⁻⁵ after 256 updates in 3620 s. These runs do not provide comparable times to the target (Appendix E.11).

Q2 (deeper hierarchies). FS2 uses two levels, sizing the coarse problem to an L2 capacity budget (Section 3). On our instances, the coarse stage is either cheap or the smaller part of the solve. In the table of General Response, item 1, the four ε = 0.01 problems return without fine updates in 0.090–0.815 s each. Where FS2 refines, on C, 2²¹, ε = 0.001, coarse kernels take 2.94 s against 12.30 s for fine kernels (Table 1a), and on Quijote the fine stage begins within the first 3% of each run's time. A third level could reduce coarse work, but remains untested.

Reviewer_NWJtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents a GPU solver for optimal transport on low-dimensional point clouds. It first solves a smaller problem using groups of nearby points, then refines the result with block-sparse updates when needed. The experiments report reaching the target accuracy on synthetic problems and solving two 134-million-point clouds on one A100 in under 2.5 hours.

Critical strengths
  1. The scale is impressive, handling this many points on a single GPU. I also like the profiling and ablations. They show how much comes from solving at a coarse level, skipping unnecessary point pairs, and using the GPU efficiently. Comparing the GPU kernels on the same sparse mask helps separate the execution gain from the reduction in work.
Critical weaknesses
  1. It is a little hard to judge how much of the large speedup comes from better automatic settings. In Appendix E.3, matching GeomLoss's coarse resolution reduces one gap from 212x to 1.4x, with both results meeting the accuracy target. Choosing good settings automatically is useful in itself, and the authors do report this comparison. Still, it covers only two inputs, so a broader comparison would help show how much advantage remains after tuning the baseline.

  2. Memory is a practical limitation. Table 1 reports about 8-10x the baseline memory. The paper is clear about this tradeoff. Table 3 shows a case that larger blocks reduce peak memory from 16.17 to 6.88 GiB. I would like to understand whether the automatic selection can make this tradeoff under a user-specified memory budget. I see this as a limitation to clarify rather than a reason by itself to reject the paper.

Questions for authors
  1. How much speedup remains with matched coarse resolutions on more inputs, at the same accuracy?

  2. Can users set a memory budget, and how much speed would that cost?

2 comments
AuthorsOpenReview ↗

Response to NWJt

Thank you for your review and questions.

W1/Q1 (matched resolution, see General Response, item 1). With GeomLoss offline-tuned at FS2's coarse resolution and both solvers meeting the same residual target, automatic FS2 is 1.35–2.28× faster on six of eight problems, and offline-tuned FS2 is faster on seven of eight. These include problems FS2 solves without fine updates and problems that need them. The larger 74–645× speedups, automatic FS2 against automatic GeomLoss, come from FS2's automatic choice of cells and its checked coarse solution.

W2/Q2 (memory budget). Users can adjust the block size B manually to trade memory for runtime; the current selector does not accept a user-specified GPU memory budget. On clustered 2²³ at ε = 0.001, B = 256 instead of the selected 128 lowers the PyTorch allocator peak from 16.17 to 6.88 GiB (2.35×), while time rises from 45.38 to 48.52 s (7%) at the same returned residual. The 2²⁷ solve, with the selector's B = 256, fits on one 80 GiB A100.

Thanks for the response. I have no further questions and will keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers. All four highlight the scale, EOT between two 1.34×10⁸-particle measures on one A100, and three value the ablations, profiling and independent residual checks (NWJt, 8Dp5, imri).

1. FS2 at matched resolution and the same residual target (NWJt W1/Q1, GXFR Q1, 8Dp5 W1/Q1). We compare runs that meet the same marginal-residual target τ. In the automatic setting, FS2 uses the same policy on every input, with sampled stopping checks included in its solve time. GeomLoss uses its default settings.

For offline tuning, we use full residuals to select, per input, the fastest passing GeomLoss configuration at the tested source-cell count closest to FS2's (varying scaling, truncation and updates), or the update counts of dense FlashSinkhorn and FS2. The search and residual checks are outside the reported times. Offline-tuned FS2 keeps its automatic cells and masks and skips sampled checks.

The new experiments show that FS2 is faster on most tested problems.

Times are medians of three warmed calls on one A100, in seconds, and each reported time is for an output that passed a full marginal check at τ = 0.005 (Appendix E.9). Automatic GeomLoss does not meet the target on six problems (R = 0.014–0.073). Tuned FS2 was measured in separate runs that re-time tuned GeomLoss within 2%. C and H are clustered and heterogeneous inputs:

InputεFS2 automaticFS2 tunedGeomLoss automaticGeomLoss tuned
C, 2²⁰0.0014.2123.080R > τ5.677
C, 2²¹0.00115.37513.309R > τ8.638
C, 2²⁰0.010.2770.169R > τ0.497
C, 2²¹0.010.8150.494R > τ1.130
H, 2²⁰0.0011.8231.620R > τ4.148
H, 2²¹0.0017.0640.297R > τ0.449
H, 2²⁰0.010.0900.07914.8810.130
H, 2²¹0.010.2730.25557.8050.392
  • Automatic FS2 vs. Automatic GeomLoss. Across the paper's grid, FS2 is 74–645× faster on the ten problems where both meet τ. On all ten, FS2 returns lifted coarse potentials without fine updates, so the speedups come from its coarse stage.
  • Automatic FS2 vs. Offline-tuned GeomLoss. FS2 is 1.35–2.28× faster on six of eight problems.
  • Offline-tuned FS2 vs. Offline-tuned GeomLoss. FS2 is 1.5–2.9× faster on seven of eight problems. On H, 2²¹, ε = 0.001, the first lift has full residual R = 0.00494 < τ. The sampled mean plus three standard errors is 0.00510 > τ, so automatic FS2 rejects it and takes 7.064 s. Offline tuning selects the first lift and returns in 0.297 s. GeomLoss wins only on C, 2²¹, ε = 0.001.

Even offline-tuned, dense FlashSinkhorn takes 285× automatic FS2's time to reach the same target, and with the same fine updates the sparse solve is 8.00× faster than the dense one (8Dp5 W1/Q1).

2. What FS2 adds (GXFR W1, imri W1). FS2 efficiently screens block pairs on a GPU with a bound on the dropped mass, at the scale of 10⁸ points per measure. It keeps Schmitzer's (2019) truncation principle and block relaxation and redesigns the rest for the GPU.

Against Schmitzer (2019), whose reported experiments ran on one CPU core:

  • Storage. Schmitzer stores one kernel entry per retained point pair. FS2 stores one index per admitted tile and recomputes its entries on chip. On the 2²⁷ solve, the admitted tiles hold 1.6×10¹² point pairs, which would take 11.7 TiB at 8 bytes per stored entry. FS2's index takes 2.9 GiB.
  • Screening. Schmitzer recursively refines a cell hierarchy down to point pairs. FS2 screens block pairs in parallel and retains whole B×B tiles. Each tile pairs two contiguous Morton-ordered runs, read with coalesced loads and scored on tensor cores. On the profiled problem, the sparse kernel evaluates 5.9% of the dense update's pairs at nearly the dense per-pair cost, so its kernel time is 14× shorter (Table 1b).
  • Threshold. Schmitzer uses a uniform threshold. FS2 sets its threshold by block mass, so each omitted tile drops at most a fixed fraction of the row's weight aᵢ (Theorem 1). With unequal block masses it admits up to 5.3% fewer tiles than a uniform rule using the largest block mass (Appendix C.3).

Against GeomLoss, the GPU multiscale solver:

  • Bounded mask. GeomLoss's centroid-cost mask does not provide a dropped-mass bound. FS2's does, and Theorem 1's residual bound, evaluated post hoc, is below τ at all 19 returns we evaluated (imri W2).
  • Fine-update execution. On the same mask and potentials, a fine update with GeomLoss's FP32 KeOps executor takes 1.57× as long as with FS2's TF32 tensor-core kernels and executes 2.3× more instructions per pair (Table 1b).
  • Checking the coarse solution. GeomLoss does not check the lifted potentials on the original points. FS2 checks sampled rows and columns before it returns them.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.