{"id":"aca34fa6-0d8b-4703-9469-b06cf7817746","arxiv_id":"2507.23602","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Error-controlled truncation, R-tree queries, multilevel hierarchies, and epsilon scheduling make large-scale finite-element entropy-regularized semi-discrete optimal transport practical.","lead":"This paper presents a set of computational accelerations for entropy-regularized semi-discrete optimal transport, including distance cutoffs with R-trees, coarse-to-fine solving, and epsilon annealing. The open-source C++ library is applied to 3D vascular shape analysis, registration, and blue-noise sampling, with up to 175x speedup in benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"175x speedup lacks an end-to-end accuracy check at the 116,305-point scale; the moving geometric cutoff and unverified softmax warm start mean the reported gradient tolerance certifies only a truncated, path-dependent objective.","rationale":"The reader's softmax concern is legitimate: Eq. (25) is a standard softmin c-transform but is used without a derivation or an error bound, and Target-only/Combined rely on it. I partially agree. I would shift emphasis: the more decisive missing support is end-to-end accuracy at the scale of the headline claim. Table 1's Erel is small but only isolates truncation at N=14,761; Table 3 never reports any error measure for the 116,305-point cases. Because Cgeom is updated from the current psi (Eq. 23, Figure 3), the convergence theory in Section 3.4 applies to a fixed objective, while the implemented algorithm minimizes a sequence of truncated objectives. The open-source code and the conservative Appendix B derivation are real supporting evidence, but they do not close this gap. The recommended verdict stays CONDITIONAL: the engineering demonstration is strong, but the headline speedup lacks a direct accuracy check at scale.","tokens_in":38524,"tokens_out":12729,"duration_ms":152805,"concrete_test":"Rerun the Target-only custom-density case of Table 3, but at the returned psi* compute (i) the untruncated gradient norm ||grad J_eps(psi*)||_1 on the finest level (no truncation) and (ii) the relative dual-functional error |J_eps(psi*) - J_eps(psi_ref)| / |J_eps(psi_ref)|, where psi_ref is obtained by continuing the standard single-level solve to convergence with no truncation (or a very tight tau=1e-12 reference). If either exceeds delta_tol or tau, the speedup is not at the claimed accuracy. Recording Cgeom at the first and last L-BFGS iterations would also show how much the optimized objective changes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central speedup claim (Section 6.1.2, Table 3) is reported as wall-clock time and fine-level iteration counts, with no error metric for the 116,305-point solutions. The only reported Erel (Table 1, Eq. 27) is for a 14,761-point problem and measures truncation error against a no-truncation discretization of the same functional, not the accuracy of the multilevel result. This gap is load-bearing because the optimization is not run against a fixed objective: the geometric cutoff Cgeom in Eq. (23) depends on the current psi through M, m, and J_eps(psi), and Figure 3 shows cutoffs varying across iterations. Appendix B's bound is derived for a fixed psi, so updating C during L-BFGS means ||grad J_trunc(psi)||_1 <= delta_tol certifies only a truncated, changing functional. The softmax warm start Eq. (25) is likewise asserted without an error estimate, so 'one fine-level iteration' is not supported by theory. Without an untruncated reference comparison, the possibility remains that the 175x speedup is achieved at lower effective accuracy than the baseline.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a suite of numerical strategies for solving entropy-regularized semi-discrete optimal transport (RSOT) problems in which the continuous source measure is discretized by finite elements. The main components are: (i) adaptive truncation of the Gibbs kernel using pointwise, integral, or geometric cutoffs, accelerated by R-tree spatial queries; (ii) multilevel schemes that coarsen the source mesh, the target measure, or both, with a softmax refinement formula (Eq. (25)) for transferring potentials between target levels; and (iii) epsilon-scaling for continuation toward small regularization parameters. The authors report wall-clock speedups of up to 175x on a 116,305-point target problem, and demonstrate the framework on Wasserstein barycenters, shape registration, and blue noise sampling. An open-source C++ implementation based on deal.II and Kokkos is provided.","tokens_in":38789,"tokens_out":3949,"duration_ms":44374,"significance":"If the reported speedups are accompanied by verified accuracy, this would be a practically important contribution to computational optimal transport, enabling RSOT at scales relevant to PDE-constrained applications. The paper has clear strengths: the code is released, the benchmarks are extensive and use non-trivial PDE-derived densities, and the truncation bounds in Appendix B are derived from first principles rather than fitted. The convergence study in Section 6.1.3 provides a falsifiable check that the regularized solution approaches the unregularized one. However, the central claim of large-scale speedup currently lacks an accuracy validation at the scale where the speedup is reported, and the softmax refinement that drives the multilevel acceleration is asserted without a derivation or error bound. These gaps must be closed before the performance claims can be fully credited.","major_comments":[{"comment":"The headline 175x speedup on the 116,305-point problem is reported as wall-clock time and fine-level iteration counts, but no accuracy metric is given for the solutions produced at this scale. The only relative error Erel (Eq. (27)) appears in Table 1 for a 14,761-point problem and compares truncation strategies against a no-truncation discretization of the same functional; it does not compare the multilevel solver against an untruncated or independently computed reference. Without such a comparison, the reported speedup cannot be separated from the possibility that the adaptive truncation and early stopping accept a less accurate solution. I recommend adding an end-to-end accuracy check at the large scale, for example by computing the untruncated dual functional value at the final multilevel potential, or by comparing against a reference solution on the fine level obtained with a more conservative tolerance.","section":"Section 6.1.2, Table 3"},{"comment":"The geometric truncation bound is derived for a fixed potential psi, but the implementation updates Cgeom during L-BFGS iterations using the current M, m, and J_eps(psi); Figure 3 shows the cutoff varying across iterations. Consequently, the stopping criterion ||grad J_trunc(psi)||_1 <= delta_tol certifies only the gradient of a truncated functional that changes along the optimization path. Appendix B provides no bound on ||grad J_eps - grad J_trunc|| and no bound on the distance between the minimizer of the truncated and the full functional. This is load-bearing because the multilevel speedup is measured in iterations to satisfy the truncated gradient criterion, not the gradient of the original objective. The paper should either prove a uniform-in-psi truncation error estimate or empirically demonstrate that the truncation error in the gradient remains controlled throughout the optimization.","section":"Section 4.1, Eq. (23), Appendix B"},{"comment":"The softmax refinement formula is asserted without derivation. The text calls it 'analogous to one half-step of a Sinkhorn-like iteration,' but no error estimate is given relating the produced initial guess to the minimizer on the finer level. The Target-only and Combined strategies, which deliver the largest reported speedups, rely on this warm start to achieve one or two fine-level iterations. The paper should provide a derivation showing that Eq. (25) is the epsilon-smoothed c-transform of the coarse potential, and ideally an error bound, or at least report the gradient norm of the warm-started solution on the fine level to substantiate the claim that it is near-optimal.","section":"Section 5.2, Eq. (25)"}],"minor_comments":[{"comment":"The Integral bound with tau=1e-4 for the uniform density is marked as not converging (✗) despite an Erel of 1.7e-4, and the text states that the prescribed tau is not always a direct predictor of observed Erel because D(psi,C) is estimated from the previous iteration. This means the global relative error guarantee in Eq. (21) is not enforced in practice; this limitation should be stated explicitly in Section 4.1 where the bound is introduced, not only in the note under Table 1.","section":"Table 1, Section 6.1.1"},{"comment":"All timings are reported as single runs without a measure of variance. Since the paper draws strong quantitative conclusions such as 175x speedup and 29.5% improvement from epsilon-scaling, at least a few repeats or a statement that timings were stable would strengthen reproducibility.","section":"Section 6.1.2 and Section 6.1.3"},{"comment":"The proof contains a few minor presentation issues: in the displayed estimate the term h^{2r-k}||f||_{C^{2r-k}}||rho||_1 is missing a closing parenthesis, and the equi-continuity claim is stated briefly. These do not affect the validity of the argument but should be cleaned up.","section":"Appendix A, proof of Theorem 3.2"},{"comment":"There are several typos and grammatical errors, e.g., 'probablity' (Algorithm 5), 'An analogous results holdf' (Section 6.2), 'conditioned praobability' (Algorithm 5), and 'fails' for 'falls' in some places. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reports a significant engineering achievement with a released codebase and extensive experiments. However, the central performance claim currently rests on an accuracy check at a smaller scale than the headline result, and the multilevel warm-start formula is unverified theoretically. Both issues are fixable within the scope of the paper: add a large-scale accuracy comparison against an untruncated reference, and either derive an error bound for Eq. (25) or provide empirical validation of the warm-start quality. The paper would then be suitable for publication in a numerical analysis venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading and worth refereeing. The real contribution is showing that entropy-regularized semi-discrete OT can be made practical at FE scale by combining distance truncation with R-trees, multilevel source/target hierarchies, and epsilon annealing. The Cgeom/Cint error bounds are derived rather than fitted, and the softmax refinement for target hierarchies is genuinely new as far as I know. The code is released. That is real evidence and should count in the paper's favor.\n\nThe benchmarks are extensive: 3D Darcy-derived densities, up to 116k target points, 480 cores. Target-only and combined multilevel converge in one or two fine-level iterations, and the reported 175x speedup over their own single-level baseline is plausible. The source-side multilevel being much slower is an honest data point. The truncation experiments in Table 1 are useful; the geometric bound is robust and delivers Erel around 1e-13. The applications to barycenters, registration, and blue noise are reasonable demonstrations rather than overclaiming.\n\nThe main soft spot matches the stress-test: the 175x speedup is wall-clock against a baseline that times out, with no end-to-end accuracy measure at the 116k scale. The Erel reported is against a no-truncation discretization of the same functional at 14,761 points, not against an untruncated or converged reference at scale. Also, the geometric cutoff depends on the current psi, so the gradient-norm stopping criterion certifies a changing truncated objective; Appendix B's bound is derived for fixed psi. That does not kill the paper, but it means 'one fine-level iteration' is an empirical observation, not a guaranteed property. The softmax refinement formula (Eq. 25) is asserted without derivation or error bound; since Target-only and Combined both depend on it, a derivation or at least a sensitivity study would strengthen the claim. Minor points: timings appear to be single runs with no variance, and Table 1 shows the Integral bound with tau=1e-4 failing for uniform density, so the default choice of geometric bound is partly post hoc. These are fixable with a reference computation at moderate scale and a few replicated timings.\n\nWho is this for? People doing computational OT at PDE scale, especially with FE-based source densities. It is not a paradigm shift, but it is a solid, useful advance with real engineering substance. I would send it to a serious referee, and I would ask for the end-to-end accuracy check and the softmax derivation before accepting.","headline":"Useful engineering paper with real speedups and open code; the big 175x claim needs an end-to-end accuracy check before I'd fully trust it.","tokens_in":39291,"tokens_out":1540,"would_cite":true,"duration_ms":15702,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49Q22","65K10","65M60"],"pacs":[],"model":"deepseek-v4-flash","headline":"A strategy combining geometric truncation, R-tree indexing, and multilevel refinement makes entropy-regularized semi-discrete optimal transport feasible at large scale.","keywords":["optimal transport","semi-discrete optimal transport","entropic regularization","finite element method","multilevel acceleration","R-tree spatial index","L-BFGS","Wasserstein barycenter"],"falsifier":"Run the target-only or combined multilevel solver on the 116,305-point benchmark while replacing the softmax warm start with simple injection (copying each coarse potential to all child points); if the fine-level iteration count does not jump from one or two back toward hundreds, the claimed speedup is not attributable to the refinement formula. Separately, fix a tolerance tau and measure the actual relative dual-functional error across many random target sets: the geometric bound claims E_rel <= tau, so any instance where the observed relative error exceeds tau falsifies the global error-control statement.","tokens_in":38348,"feed_emoji":"⚡","tokens_out":5725,"duration_ms":56985,"temperature":0.7,"pith_summary":"The paper claims that entropy-regularized semi-discrete optimal transport (RSOT), which moves a continuous, finite-element-discretized source measure onto many discrete target points, can be made practical at scale by attacking both per-iteration cost and iteration count. It accelerates each dual objective and gradient evaluation by truncating the Gibbs kernel to nearby targets and querying them with R-trees, and it cuts the number of costly fine-level iterations by solving on coarse-to-fine hierarchies of both the source mesh and the target set. On a 116,305-target benchmark derived from PDE solutions, the combined strategies converge in 373 seconds (custom density) and 239 seconds (uniform density), against 65,369 seconds or a 24-hour timeout for the single-level solver, giving up to a 175-fold speedup. The authors also show the framework makes Wasserstein barycenters, shape registration, and blue-noise sampling on manifolds practical.","feed_headline":"Multilevel solver makes 116,305-point optimal transport 175x faster","feed_subtitle":"Truncation, R-tree queries, and coarse-to-fine warm starts cut wall-clock time from over 18 hours to under 7 minutes.","key_machinery":"The load-bearing object is the reduced dual functional J_epsilon(psi) of Eq. (10), whose minimizer enforces the target marginal constraints. The two devices that carry the argument are the geometric truncation bound of Eq. (23), which converts a user tolerance tau into a cost cutoff with guaranteed relative error control, and the softmax refinement formula of Eq. (25), which converts a coarse-level dual potential into a near-optimal warm start for the next target level by computing a negative epsilon-smoothed c-transform. R-trees supply the fast spatial range queries, and L-BFGS performs the optimization of the convex dual.","core_discovery":"The central claim is that the bottleneck of RSOT, the dense O(N_q N) interaction sum between source quadrature points and target points, can be removed without losing control of accuracy, and the remaining iterations can be reduced by continuation on hierarchies. The paper derives a geometric truncation bound C_geom that, up to a user tolerance tau, guarantees the relative error in the dual functional stays small, so each quadrature point only sums targets within an adaptively computed cost radius. R-trees make the range queries cheap, with per-point cost closer to O(log N). On top of this, a source-mesh hierarchy and a k-means target hierarchy feed coarse solutions forward; the target-only and combined strategies transfer potentials with a softmax refinement formula (Eq. 25) that mimics half a Sinkhorn step. The numerical result is that on the 116,305-point benchmark, the best multilevel strategies solve in 373 seconds (custom density) and 239 seconds (uniform density), while the standard single-level solver takes 65,369 seconds or times out, a speedup of up to 175x.","pith_inferences":["The speedup claim is contingent on the softmax refinement formula being an accurate warm start; the paper neither derives it nor gives an error bound, so a reader should treat the 175x figure as heuristic rather than certified.","A per-quadrature-point adaptive truncation radius, rather than a single global cutoff, could recover the speed of the aggressive pointwise strategy while keeping the convergence guarantee of the geometric bound.","Because the expensive kernel evaluation is the same one that dominates fully discrete regularized OT, the truncation-plus-spatial-index acceleration is a natural candidate for GPU kernels, and the paper's preliminary GPU results suggest the CPU-only timings understate what is achievable on accelerator hardware.","The demonstrated convergence of psi*_epsilon to the unregularized potential psi*_0 suggests the solver can serve as a robust continuation engine toward the unregularized transport plan, which matters for applications such as optical design that live in the epsilon-to-zero limit."],"forward_implications":["RSOT with finite-element source measures and hundreds of thousands of target points becomes a minutes-scale computation instead of an overnight one.","The epsilon-scaling schedule lets a single run produce solutions across a range of regularization parameters, and the regularized potentials converge to the unregularized SOT solution as epsilon goes to zero, with relative error around 8.0e-4 at epsilon about 1e-4 in the reported test.","Nested algorithms that require repeated RSOT solves, such as Wasserstein barycenters, Lloyd-type quantization, and shape registration, inherit the acceleration directly.","The framework extends to non-Euclidean squared-geodesic costs, as demonstrated by blue-noise sampling on a sphere with a manifold-aware Lloyd iteration."],"supporting_citations":[{"why":"derives the reduced convex dual functional J_epsilon and its log-sum-exp form that the paper minimizes.","marker":"[54]"},{"why":"supplies the entropic-regularization viewpoint and the Sinkhorn iteration family that the L-BFGS approach is compared against.","marker":"[20]"},{"why":"is the spatial index structure that makes the truncation range queries fast during dual evaluation.","marker":"[33]"},{"why":"introduces the coarse-to-fine target hierarchy that the paper extends to the regularized finite-element setting.","marker":"[51]"},{"why":"provides surface mesh simplification for source hierarchies and the exact power-diagram solver used for ground-truth unregularized potentials.","marker":"[45]"},{"why":"supplies the finite-element discretization machinery that the implementation uses for meshes, quadrature, and parallel assembly.","marker":"[8]"}],"fun_headline_variants":["175x speedup for entropy-regularized semi-discrete OT","116k-point optimal transport 175x faster via new solver","From 18 hours to 7 minutes: entropy-regularized transport made fast","Truncation, R-trees, and multilevel: 175x faster OT","Semi-discrete optimal transport: new strategies give 175x speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The multilevel speedup depends on the softmax refinement formula (Eq. 25) giving an accurate warm start for the fine target level; the paper uses it without a derivation or error bound, and the strategies that reach 175x rely on it.","fun_headline_variants_meta":{"raw":{"variants":["175x speedup for entropy-regularized semi-discrete OT","116k-point optimal transport 175x faster via new solver","From 18 hours to 7 minutes: entropy-regularized transport made fast","Truncation, R-trees, and multilevel: 175x faster OT","Semi-discrete optimal transport: new strategies give 175x speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00119,"raw_usage":{"total_tokens":4952,"prompt_tokens":1028,"completion_tokens":3924,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":644,"completion_tokens_details":{"reasoning_tokens":3825}},"tokens_in":644,"tokens_out":3924,"duration_ms":30629,"temperature":1.0,"reasoning_tokens":3825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T10:32:49.155217+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the target-only or combined multilevel solver on the 116,305-point benchmark while replacing the softmax warm start with simple injection (copying each coarse potential to all child points); if the fine-level iteration count does not jump from one or two back toward hundreds, the claimed speedup is not attributable to the refinement formula. Separately, fix a tolerance tau and measure the actual relative dual-functional error across many random target sets: the geometric bound claims E_rel <= tau, so any instance where the observed relative error exceeds tau falsifies the global error-control statement.","supporting_citations":[{"cited_title":"Computational Optimal Transport: With Applications to Data Science","cited_arxiv_id":null,"evidence_quote":"derives the reduced convex dual functional J_epsilon and its log-sum-exp form that the paper minimizes."},{"cited_title":"Sinkhorn Distances: Lightspeed Computation of Optimal Transport","cited_arxiv_id":null,"evidence_quote":"supplies the entropic-regularization viewpoint and the Sinkhorn iteration family that the L-BFGS approach is compared against."},{"cited_title":"R-trees: a dynamic index structure for spatial searching","cited_arxiv_id":null,"evidence_quote":"is the spatial index structure that makes the truncation range queries fast during dual evaluation."},{"cited_title":"A Multiscale Approach to Optimal Transport","cited_arxiv_id":null,"evidence_quote":"introduces the coarse-to-fine target hierarchy that the paper extends to the regularized finite-element setting."},{"cited_title":"Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration","cited_arxiv_id":null,"evidence_quote":"provides surface mesh simplification for source hierarchies and the exact power-diagram solver used for ground-truth unregularized potentials."}],"review_version":1}