acceptodds
Under review as a conference paper at ICLR 2027

Fast LapSum: Exact Differentiable Top- at Million Scale

Abstract

Selecting the top- elements is a fundamental operation for inducing sparsity in large-scale models and optimization problems, enabling robust expert activation, token routing or attention pruning. However, hard top- is non-differentiable, while existing differentiable alternatives become increasingly expensive as the number of coordinates grows. We introduce Fast LapSum, a scalable solver for the LapSum soft top- formulation that preserves an exact selection mass of , while supporting end-to-end differentiation. In Fast LapSum, we reduce sorting cost using probabilistic bracketing, which restricts sorting to a narrow band of scores around the threshold using a binomial order-statistic from kernel-noised samples. A certification pass upgrades the probabilistic localization to a verified one at the cost of one additional linear pass, with a full-sort fallback that covers the worst-case scenario. Our certified GPU implementation processes , , and scores in median times of , , and ms, respectively, making exact-budget soft top- practical within million-scale optimization loops. We demonstrate this capability in two applications: megapixel sparse adversarial examples with a small fraction of initial image pixels, where Fast LapSum achieves an order-of-magnitude speedup over state-of-the-art methods, and 3D Gaussian splatting. In the latter, we use Fast LapSum to reduce the number of Gaussians produced by Adaptive Density Control to a substantially smaller number while retaining nearly the same rendering quality and massively reducing computation. These results demonstrate that exact-budget differentiable top- can be incorporated into practical million-scale optimization pipelines.

Primary area:
optimization
Keywords:
differentiable top-k, soft top-k, GPU acceleration

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 2 reviews, above 85% of the others.
Reviewer_8hWwOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Fast LapSum accelerates the threshold solve for the existing LapSum soft top-k operator using a GPU scan and sampled bracketing with endpoint certification and a full-sort fallback. This work evaluates operator scaling and applications to learned Gaussian pruning and sparse adversarial optimization while preserving the soft mask's total selection mass.

Critical strengths
  • Localizing the solve while retaining the outside scores through aggregated tail contributions is useful for scaling an exact-budget soft operator.

  • The large-scene experiments provide evidence beyond isolated kernel timings.

Critical weaknesses
  • The algorithmic contribution and baseline attribution relative to the original LapSum need clarification. https://arxiv.org/abs/2503.06242 already give forward/backward recurrences, prefix-scan parallelization, and closed-form inversion after sorting. The current paper acknowledges the inherited interval structure, but should distinguish the new GPU organization and sampled bracketing from those existing ideas.

  • The stated exact solver is incomplete for some valid inputs. In Algorithm 1, take r=(0,0,0,0), k=3, and t=1. Every node value is Psi(0)=2, so the lookup for the first node with Psi>=k has no result, although the correct threshold exists and equals -log(2). Appendix B does not specify this lower exterior interval. The issue also occurs for distinct, closely spaced scores. Appendix C discusses exterior cases for the middle set, but the full-sort fallback still needs a complete definition.

  • Appendix D.1 does not justify treating the threshold count as hypergeometric when Laplace noise is added. For n=K=2, zero scores, and b=0, fresh independent noise gives a Binomial(2,1/2) count despite sampling without replacement. Clarification is needed on the noise model, and the coverage bound also requires further justification.

Questions for authors
  1. Which implementations and revisions produced the LapSum results in Tables 6, 8, and 9?

  2. How does the implementation handle a root below all sorted scores, including the counterexample above?

  3. For sampling without replacement, is Laplace noise redrawn independently or fixed for each population element?

4 comments

We are thankful for preparing the detailed review.

Implementations in Tables 6, 8, and 9. Table 6 is an implementation ablation of the Fast LapSum full-solve branch. It compares a local 60-step PyTorch bisection reference with three progressively optimized full-sort implementations: PyTorch scan, cooperative CUDA scan, and fused CUDA scan. The table contains no separate benchmark of the original LapSum implementation. Its 72.6×72.6\times speedup measures the combined effect of these implementation stages relative to the reference.

The LapSum entries in Tables 8 and 9 use the original LapSum CUDA algorithm, with full sorting, interval search, closed-form threshold evaluation, and the analytical VJP. We will clarify the text and captions to distinguish the Table 6 ablation from the remaining LapSum comparisons. However, to demonstrate a clear advantage of our approach, we updated Table 8 with the full-sort branch of Fast LapSum. The Speedup is calculated between the bracketing and the full-sort modes of FLS. We achieved two orders of magnitude improvement in the calculation time for n=108n=10^8.

nnLapSum (ms)FLS full-sort (ms)FLS bracket (ms)FLS p95 (ms)Retry (%)Fallback (%)Speedup
10610^662.6887.5121.1381.162006.6×
3×1063\times10^6192.24435.1191.1851.2210029.6×
10710^7640.426140.8292.3942.4610058.8×
3×1073\times10^72145.129312.1115.44915.93920057.3×
10810^87769.5031448.43015.75144.27320092.0×
3×1083\times10^823676.7754356.87990.929131.32580047,9×

Root below all sorted scores and the full-sort fallback. The implementation handles this case through an explicit exterior-root branch. Let s1≥⋯≥sns_1\ge\cdots\ge s_n be the sorted scores. When k>Ψr(sn)k>\Psi_r(s_n), the root lies below sns_n and satisfies n−12∑ie(b−si)/t=kn-\frac12\sum_i e^{(b-s_i)/t}=k. With S−=∑ie(sn−si)/tS_-=\sum_i e^{(s_n-s_i)/t}, the solution is b=sn+tlog⁡(2(n−k)/S−)b=s_n+t\log(2(n-k)/S_-). For four zero scores, t=1t=1, and k=3k=3, this gives b=−log⁡2b=-\log 2 and four weights of 3/43/4.

We will include this condition and formula explicitly in the full-sort solver and fallback specification, so that the definition covers the case where no sorted node satisfies Ψr(si)≥k\Psi_r(s_i)\ge k. The full-sort implementation passed regression tests for this case with four zero scores at k=3k=3 and 17 near-zero scores at k=16k=16.

Noise and sampling. For sampling without replacement, fresh independent Laplace noise is redrawn for each selected element at every invocation of the procedure (it is not fixed for each population element).

We thank the reviewer for pointing out this critical subtlety. As the reviewer correctly demonstrated with the n=K=2n=K=2 counterexample, drawing fresh noise means the threshold count CC is a mixture of Poisson-Binomial distributions rather than a hypergeometric variable, making the previous hypergeometric argument incorrect. In the revised manuscript, we have updated Appendix D.1 to rigorously handle fresh noise:

  • We explicitly state the fresh noise model.
  • We prove a sub-binomial MGF dominance bound (E[eλC]≤(1−q+qeλ)K\mathbb{E}[e^{\lambda C}] \le (1-q+qe^\lambda)^K) using Maclaurin's inequality for elementary symmetric polynomials (Lemma 1).
  • Using this MGF dominance, we derive exact, closed-form Bernstein concentration bounds that formally guarantee the required threshold coverage 1−δ1-\delta without relying on hypergeometric assumptions.

Dear Reviewer 8hWw,

Thank you once again for the time devoted to preparing the review of our paper. As we believe we have addressed all the remarks, we kindly ask you to reevaluate the score. In case of any further questions, we will be happy to answer them.

Thank you for the rebuttal. The explanation of the exterior-root case addresses one of my concerns. However, the additional profiling indicates that the large speedups over the full-sort branch are strongly affected by its limited GPU parallelism. In the A100 comparison provided to Reviewer ZV7t, the speedup over CUDA bisection is approximately 2.08x at 10^8 scores and 1.0x at 3×10^8 scores. The magnitude and attribution of the incremental performance benefit therefore remain a concern.

Overall, I intend to maintain my original score.

Dear Reviewer 8hWw,

Thank you for confirming that the exterior-root formulas resolve your correctness concern. Regarding the runtime comparison with 60-step CUDA bisection, it is important to account for score distributions as well as dynamic range and temperature (τ\tau). As calculated in the benchmark for Reviewer ZV7t, scores with standard normal distribution (N(0,1)\mathcal{N}(0,1), τ=1\tau=1) represent the best-case scenario for fixed-step bisection due to their narrow initial bracket width W=max⁡(x)−min⁡(x)W = \max(x) - \min(x) and smooth local slope. Under heavy-tailed logits, outlier scores, small temperatures (τ≪1\tau \ll 1, e.g. when annealing τ\tau toward hard selection in 3DGS pruning or adversarial attacks), or tightly clustered scores (steep local slope S′(t∗)S'(t^\ast)), fixed-step bisection suffers threshold error Δt\Delta t that distorts both the soft budget and the backward VJP weights exp⁡(−∣xi−t∗∣/τ)\exp(-\vert{}x_i - t^*\vert{}/\tau). FLS computes the exact closed-form root independently of WW, τ\tau, or local score density.

We will include this analysis in the revised manuscript.

Reviewer_momtOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper accelerates LapSum, a differentiable soft top-k operator whose mask preserves the exact selection budget, but whose reference solver finds the threshold by bisection at high cost. Fast LapSum first replaces bisection with a scan-based exact solve after one sort. For very large inputs it then localizes the threshold by sampling noised scores and sorting only an uncertain middle band, aggregates the tail masses exactly, verifies the bracket with one extra pass, and falls back to a full sort when verification fails. Expected linear time is proven for one analyzed sampling variant while the deployed sampler is validated empirically. A CUDA implementation is much faster than the reference at very large scales, and two applications — learned pruning of 3D Gaussian Splatting that retains a small budget with almost no quality loss, and sparse adversarial attacks with the best measured success rate at every budget — demonstrate usefulness at million-coordinate scale.

Critical strengths
  1. The bracketed solver is a meaningful algorithmic addition: aggregating the two tails into augmented coefficients allows only the ambiguous middle band to be sorted while every score keeps its exact contribution to the soft budget. The paper also separates its deterministic, probabilistic, and empirical statements more explicitly than is common, proves expected-linear time only for the variant it analyzes, checks the gradient against finite differences, and reports retry and fallback rates rather than only a fast path.
  2. The systems evaluation is broad and the applications are internally well controlled: timings extend to very large scales with certification and retries included, the 3DGS study matches budgets and recovery periods across many scenes and seeds with per-scene results, and the attack comparison at megapixel scale isolates the solver change by sharing initialization, schedule, and hard masks.
Critical weaknesses
  1. The contribution is mispositioned against the closest prior work. The sorted-scan route to the threshold — sort, parallel-scan recurrences, interval lookup, and a closed-form root, including the tail intervals — is already published in the original LapSum paper, so the exact full-solve branch rederives an existing algorithm rather than introducing one. The claimed algorithmic gain is measured against a bisection implementation rather than the published closed-form solver, so the headline speedup over the reference reflects implementation strength more than algorithmic advance. The genuinely new elements — the bracketed localization, the tail aggregation that keeps the budget exact inside a bracket, and the certification protocol — are narrower than the framing suggests. Separately, as specified the algorithms omit valid boundary cases, such as a root outside the range of scores or an empty middle band, although the prose partially addresses the bracketed case.
  2. The exactness and scaling claims outrun the implementation. The endpoint certificate accepts within a tolerance, so the delivered budget exactness sits at tolerance level rather than at the claimed strict or floating-point-roundoff level, and the measured post-validation errors are consistent with the tolerance rather than below it. The largest-scale timings grow clearly faster than linearly while retries become frequent, contradicting the stated linear empirical scaling, and the score distributions and memory layouts behind the operator benchmarks are not disclosed. The attack study tunes only the proposed method on a development set without stating baseline tuning, and the 3DGS operating point is selected on scenes that are part of the final evaluation.
Questions for authors
  1. Which revision and implementation of LapSum is the bisection baseline? Please position the full-solve branch against the closed-form sorted-scan algorithm already published in the LapSum paper and benchmark against it under identical conditions, separating implementation gains from algorithmic ones.
  2. How does the implementation handle a root below or above all scores, and an empty middle band? Documented handling with boundary regression tests would resolve the specification gap.
  3. Can the certificate be made conservative so that containment is strictly proved despite floating-point evaluation, or should the strict-exactness claims be restated to match the implemented tolerance?
  4. What score distributions and memory layouts produced the operator timings, and how does runtime behave on tied, periodic, sorted, or extreme-budget inputs? The largest-scale timing appears superlinear; please temper or explain the scaling claim.
  5. Were the attack baselines tuned on the same development images as your method, and can the complete budget grid be reported?
  6. Was the 3DGS retention operating point selected using scenes that are also part of the final evaluation, and how sensitive are the conclusions to that choice?
4 comments
AuthorsOpenReview ↗

Author Response Part 1

We appreciate the time and effort put into preparing the detailed review.

Contribution and baseline implementation. We did not replace the original LapSum solver with bisection. First of all, in our calculations, the LapSum CUDA baseline preserves the original full-sort, interval-search, closed-form algorithm and analytical VJP. Secondly, in Table 8 we compare its operation time with the certified path of Fast LapSum. Additionally, to make our comparison and gain presentation fully clear, we updated Table 8 with the full-sort branch of Fast LapSum. We present above the clear advantage of our proposition, where Speedup is calculated between the bracketing and the full-sort modes of FLS.

nnLapSum (ms)FLS full-sort (ms)FLS bracket (ms)FLS p95 (ms)Retry (%)Fallback (%)Speedup
10610^662.6887.5121.1381.162006.6×
3×1063\times10^6192.24435.1191.1851.2210029.6×
10710^7640.426140.8292.3942.4610058.8×
3×1073\times10^72145.129312.1115.44915.93920057.3×
10810^87769.5031448.43015.75144.27320092.0×
3×1083\times10^823676.7754356.87990.929131.32580047,9×

Table 6 is just a separate ablation of our full-solve implementation. It compares a local 60-step PyTorch bisection reference with PyTorch scan, cooperative CUDA scan, and fused CUDA scan. The 72.6×72.6\times gain refers to this ablation. We will clarify the captions to avoid confusion of readers.

Our contribution concerns a probabilistic bracketing pipeline limiting sorting to a candidate band (bracket) and aggregating the tails. On identical A100 inputs, at n=106n=10^6, k=n/16k=n/16, LapSum CUDA, FLS full-sort, and FLS bracket take 62.688, 7.512, and 1.138 ms, respectively. Crucially, the bracket gain is 6.6$\times$ compared to the FLS full-sort mode, and increases to 92.0$\times$ at n=108n=10^8, where the respective runtimes are 7769.503, 1448.430, and 15.751 ms, respectively. This highlights the superiority of the bracketing approach over full sorting, especially for large-scale inputs.

Exterior roots and empty middle bands. Appendix C states that a root above or below all elements of LL, MM and RR, or an empty MM, is handled through the tail terms in the same equation. For a root outside the entire score range, the budget equation reduces to a single exponential. With S+=∑ie(ri−rmax⁡)/tS_+=\sum_i e^{(r_i-r_{\max})/t} and S−=∑ie(rmin⁡−ri)/tS_-=\sum_i e^{(r_{\min}-r_i)/t}, the exterior solutions are b=rmax⁡+tlog⁡(S+/(2k))b=r_{\max}+t\log(S_+/(2k)) above all scores and b=rmin⁡+tlog⁡(2(n−k)/S−)b=r_{\min}+t\log(2(n-k)/S_-) below all scores. The implementation has explicit branches for these cases. Both FLS variants passed tests with roots above and below the score range, using four zero scores (k=1,3k=1,3) and 17 near-zero scores (k=1,16k=1,16), plus a Gaussian reference case. The maximum relative budget residual was 9.08×10−89.08\times10^{-8}. For scores [−2,2][-2,2], k=1k=1, and bracket [−0.1,0.1][-0.1,0.1], the middle band is empty and the tail-only solve correctly returns b=0b=0. We will document these tests.

AuthorsOpenReview ↗

Author Response Part 2

Numerical certificate. We agree that the current CUDA endpoint check is tolerance-based. To demonstrate the feasibility of rigorous certification, we applied 53-bit interval arithmetic on CPU to a bracket generated by FLS for n=106n=10^6 standard Gaussian scores, with k=n/16k=n/16 and temperature t=1t=1. The computed endpoint masses were approximately 7.8×1047.8\times10^4 and 5.0×1045.0\times10^4, with rigorously bounded absolute errors of 8.0×10−68.0\times10^{-6} and 6.4×10−66.4\times10^{-6}. Since the resulting intervals lie strictly on opposite sides of k=62500k=62500, they certify that the bracket contains the exact threshold. The current CUDA implementation uses the tolerance τ=10−4max⁡(k,1)\tau=10^{-4}\max(k,1) documented in Appendix E. We will clarify that.

Timing inputs and scaling. The operator timings in Figure 2 use standard normally distributed Gaussian scores stored in contiguous FP32 tensors of shape 1,n1,n, with consecutive scores adjacent in GPU memory. We additionally measured bracket runtime on A100 at $n=10^6$:

Scoresk=1k=1k=n/16k=n/16k=n−1k=n-1
Gaussian1.1331.1391.221
Tied1.1071.0941.189
Periodic1.1331.1161.218
Sorted1.1093.5501.233
Narrow-range1.1241.1151.221

Times are median milliseconds on contiguous inputs. All 15 cases satisfy relative budget error 10−510^{-5}.

While Fast LapSum includes an O(Nlog⁡N)O(N \log N) full-sort fallback for extreme boundary cases, empirical benchmarks demonstrate a 0.0%0.0\% fallback rate up to N=109N = 10^9. Minor non-linearities at extreme scale (N=109N = 10^9) stem from memory bandwidth saturation and small-sample retries, not algorithmic superlinearity. At N=109N = 10^9, a single FP32 tensor score exceeds the L2 cache and must be read directly from High-Bandwidth Memory (HBM3) across the GPU memory bus. While the retry frequency increases to 60% for N=109N = 10^9, executing a few additional retries is not overwhelming due to a small number of the bracket samples compared to NN. The theoretical worst-case fallback bound of O(Nlog⁡N)O(N \log N) remains purely a safety net and does not lower performance in practice.

Attack tuning and full budget grid. In the original experiments, FLS was tuned on 100 development images disjoint from the 1000-image test set, whereas Sparse-PGD and PGD-L0L_0 used fixed configurations. To address this, we additionally tuned both baselines on the same development set, using the same search budget as FLS: eight configurations per method and model, evaluated at k∈k\in {10,100,500} with 200 steps and one restart. We selected one configuration per method and model by maximizing mean ASR across these budgets after 8-bit quantization.

The matched development-set results (ASR, %) are below.

ModelMethodk=10k=10k=100k=100k=500k=500
ConvNeXtV2-TinyFLS117399
Sparse-PGD, tuned105497
PGD-L0L_0, tuned42082
ResNet-50FLS2586100
Sparse-PGD, tuned157099
PGD-L0L_0, tuned74394

FLS achieves higher ASR at every evaluated development-set budget, outperforming tuned Sparse-PGD by an average of 7.33 percentage points on ConvNeXtV2-Tiny and 9.00 on ResNet-50. Evaluation of the tuned baselines on the held-out test set is ongoing and will be added to the paper.

For completeness, we also report the full original test-set results (ASR after 8-bit quantization, %) across all six budgets. These use 1000 test images, 500 steps, and 3 restarts. Original fixed configurations are α=β=0.25\alpha=\beta=0.25 for Sparse-PGD and step size 0.250.25 for PGD-L0L_0.

ModelMethodk=1k=1k=5k=5k=10k=10k=50k=50k=100k=100k=500k=500
ConvNeXtV2-TinyFLS1.35.811.954.478.6100.0
Sparse-PGD1.74.77.226.947.094.6
PGD-L0L_00.51.32.38.820.382.5
ResNet-50FLS3.112.824.575.292.6100.0
Sparse-PGD3.39.815.547.066.398.2
PGD-L0L_00.92.74.829.348.291.8

Retention selection and sensitivity. Yes, the reported 13-scene results include the five development scenes. Excluding them leaves eight scenes with three seeds each. FLS achieves ΔPSNR=−0.046±0.141\Delta\mathrm{PSNR}=-0.046\pm0.141 dB, compared with −0.237±0.204-0.237\pm0.204 dB for hard pruning. Its mean training time is 9.97 minutes versus 12.29 for ADC, and rendering throughput is 391.8 versus 213.9 FPS. Thus the quality and efficiency conclusions also hold on the remaining scenes and are not limited to the five scenes selected initially.

Figure 3 shows a trade-off near the selected point. At 50%, 30%, and 20% retention, mean PSNR changes are +0.044+0.044, −0.065-0.065, and −0.088-0.088 dB, with training speedups of 1.22×1.22\times, 1.32×1.32\times, and 1.37×1.37\times. At 10% retention the PSNR change reaches −0.402-0.402 dB.

The clarifications and new experiments resolve the concerns raised in my review. My assessment is unchanged; I would only encourage including the pending held-out results for the tuned baselines in the final version.

Dear Reviewer momt,

We are thankful for the effort put into reviewing our work and for acknowledging our endeavors. As soon as the pending experiments are completed, we will include them in the paper.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Author Response Part 1

We express our thanks for preparing the review.

Additional operator baselines. We have run forward comparisons on A100 using identical inputs for all methods. We compare against CUDA bisection with 60 iterations, Newton's method with 30 iterations and torch.topk. As requested, Newton is initialized at the kk-th largest score. If a Newton step falls outside the current root bracket or produces a non-finite value, we use the bracket midpoint. Timings include initialization and computation of the final soft mask.

For Gaussian scores with k=n/16k=n/16, the following median forward times are in milliseconds.

nnLapSumFLS full-sortFLS bracketBisectionNewtontorch.topk
10610^662.6887.5121.1386.20010.3090.259
3×1063\times10^6192.24435.1191.1856.19819.9270.303
10710^7640.426140.8292.3946.66093.9150.582
3×1073\times10^72145.129312.1115.44911.058341.6562.477
10810^87769.5031448.43015.75132.7991189.94418.466
3×1083\times10^823676.7754356.87990.92994.7463396.870148.323

At n=109n=10^9, both FLS variants ran out of memory on A100 40 GB in this benchmark. torch.topk propagates gradients through selected values, but not through the discrete selection of indices.

3DGS. We agree that budget accuracy alone does not establish downstream benefits. We therefore performed the requested direct comparison with DFTopK in the same 3DGS pipeline, at 30% retention across 13 scenes and three seeds per scene, with matched training schedules and identical final Gaussian counts.

At identical final Gaussian counts, Fast LapSum achieves better mean reconstruction quality on all three quality metrics (PSNR, SSIM, LPIPS) and shorter training time. While DFTopK achieves higher rendering FPS, we need to emphasize that, in contrast to Fast LapSum, DFTopK is not an exact-budget Top-K operator. Importantly, the quality advantage persists on the eight scenes excluded from DFTopK temperature tuning.

ScenesOperatorPSNR ↑SSIM ↑LPIPS ↓Train (min) ↓FPS ↑
All 13Fast LapSum27.2640.83350.223216.84217.62
All 13DFTopK27.2000.82860.234017.54235.13
8 outside tuningFast LapSum27.2670.81970.245116.73218.28
8 outside tuningDFTopK27.1860.81480.256917.33236.48

During score optimization, DFTopK exhibits a mean/max relative soft-budget error of 1.437% / 6.043%, compared with 6.31×10−66.31\times10^{-6}% / 2.42×10−52.42\times10^{-5}% for Fast LapSum (468 checkpoints per method). Although the final hard top-k step ensures identical Gaussian counts, Fast LapSum preserves the scheduled soft budget throughout optimization.

DFTopK's temperature multiplier was tuned over {0.3,1,3}\{0.3,1,3\} on five development scenes, selecting 0.3 by mean PSNR. Results are averaged across seeds within each scene and then across various scenes. All results above were measured on A100, whereas Table 1 in the paper reports measurements on GH200.

AuthorsOpenReview ↗

Author Response Part 2

Contribution and Section 4.1. Section 4.1 introduces the existing LapSum operator and its closed-form solution after sorting. The analytical VJP also comes from LapSum. All baselines labeled “LapSum” use the original LapSum operator, with the CUDA algorithm retaining full sorting, interval search, and closed-form threshold evaluation. Our novelty begins in Section 4.2. Fast LapSum restricts sorting to a bracketed middle set MM and incorporates the remaining scores through aggregated tail contributions. This accelerates evaluation of the same LapSum operator. We will make this clear in Section 4.1 explicit.

Full-sort cost. Our A100 profiling at n=108n=10^8, using identical inputs and five forward passes, shows that threshold solving dominates the full-sort runtime, taking 1433.632 ms (98.85%). In comparison, sorting takes 15.175 ms (1.05%) and the final CDF evaluation takes 0.605 ms (0.04%). The remaining 0.06% comes from auxiliary GPU operations and rounding. With bracketing, threshold solving takes only 1.371 ms (8.84%), sorting 0.194 ms (1.25%), and the final CDF evaluation 0.598 ms (3.86%). The remaining approximately 86% covers bracket construction, tail aggregation, middle-set gathering, endpoint verification and auxiliary. Thus, bracketing substantially reduces both sorting and threshold-solving costs, with the latter dominating the speedup in our implementation. The full-sort threshold kernel uses a single 256-thread CUDA block per input vector, limiting parallelism at B=1B=1. This makes the measured speedup implementation-dependent. A multi-block scan could improve the full-sort baseline, but we have not benchmarked it. Importantly, Fast LapSum also outperforms a separate 60-iteration CUDA bisection baseline, taking 15.751 ms versus 32.799 ms at n=108n=10^8, a 2.08× speedup. All measurements above use an A100, whereas the 1190.9 ms full-sort result in the paper was measured on GH200.

I thank the authors' response and additional results. My concerns are partially addressed so I will keep my original rating.

Dear Reviewer ZV7t13,

Thank you for reading our response and acknowledging the additional results. As we are committed to fully resolving your concerns before the discussion period closes, could you please specify which of your original points you feel remain only "partially addressed"?

To summarize for the AC and the discussion, our previous response provided exactly the data and comparisons requested in your initial review:

  • Large-scale operator benchmarks: We provided forward comparisons on an A100 for nn up to 3×1083\times 10^8 against CUDA bisection, Newton's method, and torch.topk, demonstrating Fast LapSum's 2.08×\textbf{2.08×} speedup over the 60-iteration bisection and 75.55×\textbf{75.55×} speedup over the Newton baseline at 10810^8.

  • Direct 3DGS pipeline evaluation: We ran the requested 13-scene comparison against DFTopK at 30% retention. The results demonstrated that Fast LapSum achieves better reconstruction quality (PSNR, SSIM, LPIPS) and faster training, while maintaining an exact budget (6.31×10−66.31\times 10^{-6} % error vs. DFTopK's 1.437% error).

  • Algorithmic and profiling clarifications: We clarified the exact boundary of our novelty (Section 4.2) and provided detailed kernel-level profiling at n=108n=10^8, confirming that threshold solving (98.85% of runtime), rather than sorting, dominates the full-sort baseline.

If there are specific flaws in the newly provided empirical data, downstream 3DGS benchmarks, or theoretical clarifications, we are ready to address them immediately. Otherwise, we kindly ask for a re-evaluation of the score in light of these substantive, direct additions to the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.