acceptodds
Under review as a conference paper at ICLR 2027

DrainSinkhorn: Instance-Resident Batched Entropic Optimal Transport on GPUs

Abstract

Many learning pipelines call entropic optimal transport (OT) inside a loop, and each call is a batch of small, independent problems: one per image in detection label assignment, per patch pair in point-cloud registration, per frame pair in tracking, and per tile in domain decomposition. General GPU solvers launch every Sinkhorn update over the whole batch and run the batch until its slowest problem stops, so practitioners write a kernel for each shape or drop OT. We present DrainSinkhorn, a batched Sinkhorn solver that makes each problem of the batch, an instance, the unit of GPU execution. Wherever an instance fits on chip, one GPU thread block solves it from start to finish and exits as soon as the instance converges, freeing its slot for a pending instance; with a fixed iteration count, several instances share a thread block, and the forward map and its exact gradient take one launch each. Larger instances leave later launches once they converge. On tracking and domain-decomposition workloads, DrainSinkhorn is 2.73–10.75× faster than OTT-JAX, the fastest general batched GPU solver in our comparison, and 5.3–34× faster than POT; the gain is largest on calls with thousands of instances. In training layers it is 1.05–2.8× faster than OTT-JAX and 9.9–24× faster than the Sinkhorn modules of OTA and GeoTransformer, cutting label assignment from 16.3% to 4.7% of each GPU's training step and making GeoTransformer's patch matching 10.4× faster in a training step.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
entropic optimal transport, Sinkhorn algorithm, GPU acceleration, batched solvers, Triton kernels

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_RNsqOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a Triton GPU solver for batches of many small, independent entropic OT problems, such as those in detection label assignment, mHC, point-cloud matching and tracking. Each small instance runs entirely on-chip in one thread block and exits as soon as it converges, which frees the slot for the next instance. Fixed-iteration training layers get packed forward kernels and exact backward kernels. Under a common accuracy gate, the solver is 2.7-10.8x faster than OTT-JAX and 5-34x faster than POT on inference workloads, and gives 1.1-1.7x end-to-end speedups in several training pipelines.

Critical strengths
  • The benchmarking is unusually careful. All methods must pass the same accuracy gate, runs are paired with bootstrap intervals, and returned solutions are audited in FP64. The authors also report the cases where their solver loses. This makes me trust the speedups. The released code matches the paper's structure and includes tests.

  • The problem is real and the workloads are well chosen. Many pipelines solve lots of small OT problems in a loop, and practitioners currently write custom kernels or drop Sinkhorn altogether. The inputs are captured from real models such as OTA, GeoTransformer and mHC, so the results are directly useful.

Critical weaknesses
  • The ML contribution is limited. The main ingredients are standard GPU techniques: one block per problem, early exit, packing, and kernels borrowed from FlashSinkhorn and LogSinkhornGPU. Proposition 1 is essentially Graham's scheduling bound. This is a well-engineered library, and it might fit MLSys or a software track better than ICLR.

  • The end-to-end impact is modest and the scope is narrow. Whole-step speedups are only 1.13x for OTA and 1.18x for GeoTransformer. The 1.73x on mHC comes from a small 34M-parameter GPT, and TileLang-mHC does slightly better on the same step. The fast paths only cover up to 64 or 128 points per side, and all results are on a single A100.

Questions for authors

Clarifications:

  • Can you show results on at least one other GPU, such as an H100? Several design choices look tied to the A100.
  • For mHC at a realistic model size, how large is the Sinkhorn share of the step, and what end-to-end speedup would you expect?
  • The supplement contains only the solver, not the benchmark scripts, the baseline wrappers or the input-capture code. Since the contribution is mainly speed, could you release these so the tables can be reproduced?
  • How would a simple one-block-per-instance kernel without release compare? This would separate the benefit of the design from the implementation.

Suggestions:

  • The citation to linear-time GNNs for recommendation in the introduction seems unrelated and could be removed.
  • A short table showing which execution path handles which problem shape would help readers.
2 comments

ML contribution and venue. Much of the recent use of Sinkhorn in machine learning is a batch of small, independent problems inside a loop. mHC projects one 4×4 residual mixing matrix per token and layer, and DeepSeek-V4 trains with it at 284B and 1.6T parameters. WASD (NeurIPS 2026) solves one OT problem per generated token when distilling large language models, PEARL (ICLR 2025) one per training prompt, supervised graph prediction (Méndez et al., 2026) one per predicted and target graph, Learn to Rank (ECCV 2026) one per image, and PLASMA (ICLR 2026) one per protein pair. These authors report the cost. WASD roughly doubles training time. Méndez et al. write that "the inner Sinkhorn rollouts dominate training time" and replace the solver with a learned matcher. For mHC, Wang and Qiu (2026) write a warp-level 4×4 solver, and later hyper-connection designs drop the Sinkhorn step. Medina and Schmitzer (2025) write their own CUDA solver for the cell problems of domain decomposition. The contribution is one solver that makes the instance the unit of GPU execution across these shapes and stopping rules, in place of a kernel per shape.

This fits the ICLR call for papers, which lists "infrastructure, software libraries, hardware, etc." among its topics. FlashSinkhorn, which we build on, was an ICML 2026 spotlight. On the ML side, the fixed-iteration path returns the exact gradient of the K-step map and stores K(N+M) numbers per instance instead of K plans. In the 2,500-step mHC runs, TileLang-mHC, whose backward is an implicit gradient at its output, stalls, while the official loop and DrainSinkhorn reach the same held-out loss (general response).

Proposition 1 applies Graham's bound for list scheduling to the GPU block scheduler. It states when release saves wall time: on batches that run in several waves, not on a single wave. On all three GPUs, release speeds up the multi-wave mot-b16 by 1.23–1.41× and the single-wave mot-b64 by 1.00–1.03×.

Kernels borrowed from FlashSinkhorn and LogSinkhornGPU. Three parts follow earlier code, as the source files and the NOTICE state. The dot-product and online log-sum-exp helpers of the indexed path are adapted from FlashSinkhorn. Our consumer kernel, which applies the plan rebuilt from the potentials without storing it, follows the organization of FlashSinkhorn's plan-apply kernel. The separable reduction follows LogSinkhornGPU and Medina and Schmitzer, and DrainSinkhorn runs it inside a resident program. The resident solves with release, the packed fixed-iteration forward and backward, the cooperative short-by-long kernel and the screen in the final stage of the row-update kernel are ours.

One-block-per-instance kernel without release. This arm is already in the paper: in §5.4 and Fig. 3(a), the same resident kernel runs every instance to D_max with the same checks. Most of the gain comes from on-chip execution, not from release or kernel code (general response).

End-to-end gains. When only the Sinkhorn solve is replaced, the whole-step speedup is at most 11−s\frac{1}{1-s}, where s is the share of the official solver in the step. In the paper's A100 runs, the Sinkhorn part of label assignment is 12.8% of the OTA step, so the bound is 1.15×, and we measure 1.13×. In GeoTransformer the OT share of the training step is 16.4%, so the bound is 1.20×, and we measure 1.18×.

TileLang-mHC on the same step. It is not the same step. TileLang-mHC's backward is an implicit gradient at its output, not the gradient of the 20-step map, which is what the asterisk marks in Table 1. In the 2,500-step runs its gradient norm before clipping grows to 116–83,279, against 0.57–0.69 for the official loop and DrainSinkhorn, and its held-out loss stalls (general response). Step times are comparable only among methods that train the same model, and among those DrainSinkhorn has the fastest step: against the official loop, a whole GPT training step is 1.73× faster with DrainSinkhorn, 1.57× with triton-sinkhorn and 1.32× with torch.compile (§5.2).

mHC at realistic size. Per token and layer, the Sinkhorn work is a 4×4 map iterated 20 times whatever the model width, while the rest of the layer grows with the square of the width, so its share falls as the model grows. The mHC paper reports a total mHC overhead of 6.7% in its large-scale training, and Sinkhorn is only part of that. The bound above then applies with this smaller share. What does not depend on scale is that DrainSinkhorn computes the exact gradient of the 20-step map, which the long runs show to matter.

Reproducibility and path table. The supplement now contains the benchmark (general response). Table 3 (§5.4) gives the execution path of every inference workload, and §3 states the path of each training layer.

LTGNN citation. We keep it. It cites another pipeline where execution organized around the workload removed a scalability bottleneck, one of the motivations of this work.

Thank you for the thorough response and the new results. The H100 and L40S experiments show that the speedups carry over to other GPUs without retuning, the breakdown of the speedup sources makes clear that most of the gain comes from on-chip execution, and the released benchmark scripts address my reproducibility concern. I also appreciate the clearer attribution of the components taken from FlashSinkhorn and LogSinkhornGPU, and I agree that the release ablation in Fig. 3(a) already answers my question about a resident kernel without release.

The 2,500-step mHC runs are a useful addition. They show that computing the exact gradient of the K-step map matters in practice, which strengthens the ML side of the paper.

My remaining reservations are the same as before, but they are about scope rather than correctness. As the authors' own bound shows, the end-to-end gain is limited by the solver's share of the step, so whole-step speedups stay modest in the OTA and GeoTransformer pipelines and will shrink for mHC at realistic model sizes. The contribution is mainly a well-engineered solver rather than a new method. Overall, I keep my score and remain positive about the paper.

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

This paper presents DrainSinkhorn, a GPU solver for batches of small, independent entropic optimal transport problems. The method improves GPU efficiency by keeping small problems on chip, allowing thread blocks to exit upon convergence, and using active-instance indexing for larger problems. It also supports fixed-iteration workloads by processing multiple instances per block and introduces a custom backward pass that stores potential histories instead of full transport plans while preserving the gradient through K iterations. Specialized kernels are provided for grid-based and short-by-long assignment problems. Experiments on MOT17, domain-decomposition workloads, OTA, mHC, and GeoTransformer show speedups of 2.73–10.75× over OTT-JAX across seven inference workloads.

Critical strengths
  1. The paper addresses an important performance bottleneck in batched optimal transport, which is widely used in applications such as object detection, tracking, and point-cloud registration.
  2. The proposed on-chip execution strategy reduces kernel launches and memory transfers, while the custom backward pass lowers memory usage without changing the finite-K gradients. The design is effective, achieving 2.73–10.75× speedups over OTT-JAX across seven inference workloads.
Critical weaknesses

The evaluation uses only an A100 GPU. Performance on other architectures remains unclear. A brief portability discussion would improve the practical guidance.

Questions for authors
  1. The solver tests several tilings on first use. The benchmarks are measured after warm-up. Could you clarify the typical search overhead?
  2. The experiments use an A100 GPU. Other architectures have different on-chip resources. How might this affect tiling and packing choices?
  3. Some instances reach the maximum iteration limit without satisfying the convergence tolerance. Please clarify how these cases affect solution accuracy.
1 comment

Other GPUs. The results are in the general response. The hardware numbers that matter:

A100H100L40S
SMs108132142
Max blocks per SM323224
Registers per SM64K64K64K

The register file decides which instances fit on chip. It is the same on all three GPUs, so the size limits do not change. The SM count and blocks per SM decide how many waves a batch needs, and so how much release helps. The packing constants stay at their A100 values, while the tiling search and the autotuning run on each GPU. Appendix C.2 adds this discussion.

Search overhead. First call in a fresh process, range over the three GPUs (Appendix C.2):

Empty cacheWarm cache
DrainSinkhorn, dd-t16 and mot-win (tiling search or autotuning)38.9–49.4 s8.96–11.1 s
DrainSinkhorn, other five workloads2.75–4.52 s0.58–0.88 s
OTT-JAX, same five workloads1.19–2.01 s0.46–0.70 s

On dd-t16 and mot-win, the first call compiles several kernel variants and times them on the calling batch to keep the fastest: the indexed path and three resident tilings on dd-t16, and several tile shapes on mot-win. With a warm cache, only the timing remains. These two workloads have the largest instances and the smallest gains in Table 2 (2.73× and 3.04×), so the main speedups do not depend on this search. The cost is paid once per process and shape, so a training loop spreads it over thousands of calls. A caller that makes only a few calls can pass autotune=False, which skips the searches and uses preset parameters.

Instances that reach the cap. On dd-t4, 84.9% of instances are within τ=10⁻⁴ for DrainSinkhorn, 84.5% for OTT-JAX and 85.1% for POT (Appendix C.7). With the cap raised fivefold, fewer than 3% still reach it, and DrainSinkhorn stays 29.5× and 37.9× faster than OTT-JAX on dd-t4 and mot-b16. Each instance returns its status, so a caller can handle capped ones separately.

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

This paper introduces a GPU implementation for batched entropic OT. It keeps small problems on chip across Sinkhorn iterations, releases converged instances, and provides specialized kernels for different shapes and fixed-step training layers.

Critical strengths
  • The practical results are quite good. The speedup also appears in whole training steps, rather than only in isolated kernel tests. For example, the mHC experiment gives a 1.73x step speedup over the reference loop, although the gain over other optimized implementations is smaller.

  • The experiments are relatively careful. The authors check outputs and gradients, isolate the benefit of release, and report cases where their method is slower. The FP64 checks and larger iteration-budget experiments also help address whether the speedup comes from lower accuracy.

Critical weaknesses
  • The novelty seems limited. For example, the original mHC paper, already uses a fused Sinkhorn kernel and backward recomputation. The authors should explain more clearly what new technical designs are needed beyond existing implementations.

  • The mHC training comparison is too short (23 steps) to assess long-term behavior. A longer comparison with TileLang would help show whether preserving the finite-step gradient makes a practical difference.

  • The paper emphasizes release, but the training speedups mainly come from other optimizations, which makes the main contribution a bit hard to follow. A table showing the execution path and source of speedup for each workload would help.

Questions for authors
  • If feasible, can a few representative results be tested on another GPU? The current evidence is limited to one A100.
2 comments

Novelty relative to mHC. mHC already fuses Sinkhorn into one kernel with an on-chip backward, and the revision credits this in §3.3 and in related work. Our fixed-iteration path adds the following:

mHC kernelDrainSinkhorn
Problem size4×4up to 128×128
Marginals and εfixedper instance
Gradientinput matrixcost, marginals and ε
Other problemsnonetolerance solves with release, separable grids, short-by-long instances

Sources of the speedup. The general response gives the breakdown, Table 3 (§5.4) gives it per workload, and the introduction now states it before the contributions. The training layers run a fixed number of iterations, so their gains come from batching, packing and solving each instance at its valid size, not from release.

Another GPU and long mHC training. Both are in the general response.

Reviewer_S9A5OpenReview ↗

Comment

Thank you authors. The responses addressed my concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

Thanks all reviewers. The revision adds the results below.

Three GPUs. We ran the submitted solver unchanged on an H100 and an L40S, with the constants chosen on the A100. All three columns come from one new run, so the A100 column differs slightly from Tables 1 and 2, which come from the original run. Speedups of DrainSinkhorn:

A100H100L40S
Inference workloads, over OTT-JAX2.64–11.1×2.21–11.6×1.70–13.4×
Label assignment, 2 images per call14.8×13.0×13.7×
OTA training step1.17×1.15×1.09×
Patch matching, forward calls11.1×10.8×11.9×
GeoTransformer training step1.20×1.24×1.14×
Crowd counting, OT loss3.52×3.25×4.43×
DM-Count training step1.59×1.17×1.47×

Sources of the speedup. Most of the speedup comes from keeping instances on chip. Release adds to it when a batch needs several waves of programs.

ChangeSpeedup
Same updates run on chip, both without release15–80×
Adding release, resident path1.00–1.55×
Adding release, indexed path (mot-win)1.67–2.12×

Table 3 (§5.4) gives this per workload, with its execution path.

Long mHC training. We trained the paper's mHC GPT for 2,500 steps with three seeds:

Final held-out loss
Official loop4.55–4.58
DrainSinkhorn4.55–4.58
TileLang-mHC6.07–6.37

TileLang-mHC computes a different quantity, marked * in Table 1. It follows the others for about 200 steps and then stalls. Appendix D.5 shows the curves.

Code. The supplement now includes the benchmark: timing scripts, baseline configurations and the scripts that capture the training-layer inputs.

Changes in the revision.

  • Introduction: recent uses of batched small Sinkhorn problems and the cost their authors report. It also states up front that most of the speedup comes from on-chip execution.
  • §3.3 and related work: credit for mHC's fused kernel and its on-chip backward.
  • §5.2: the whole-step bound for replacing only the solver, and the 2,500-step mHC training result.
  • §5.4: a new Table 3 with each workload's execution path and the sources of its speedup.
  • Appendix C and D: results on an H100 and an L40S, first-call times, and the 2,500-step training curves. The appendix is now grouped into inference workloads and training layers.
  • Table 1(b) shows forward and forward-plus-backward times in separate column groups. The baseline settings and timing details are now in the supplementary scripts.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.