- 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
-
Which implementations and revisions produced the LapSum results in Tables 6, 8, and 9?
-
How does the implementation handle a root below all sorted scores, including the counterexample above?
-
For sampling without replacement, is Laplace noise redrawn independently or fixed for each population element?
4 comments
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 (). As calculated in the benchmark for Reviewer ZV7t, scores with standard normal distribution (, ) represent the best-case scenario for fixed-step bisection due to their narrow initial bracket width and smooth local slope. Under heavy-tailed logits, outlier scores, small temperatures (, e.g. when annealing toward hard selection in 3DGS pruning or adversarial attacks), or tightly clustered scores (steep local slope ), fixed-step bisection suffers threshold error that distorts both the soft budget and the backward VJP weights . FLS computes the exact closed-form root independently of , , or local score density.
We will include this analysis in the revised manuscript.
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× 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=108.
Root below all sorted scores and the full-sort fallback. The implementation handles this case through an explicit exterior-root branch. Let s1≥⋯≥sn be the sorted scores. When k>Ψr(sn), the root lies below sn and satisfies n−21∑ie(b−si)/t=k. With S−=∑ie(sn−si)/t, the solution is b=sn+tlog(2(n−k)/S−). For four zero scores, t=1, and k=3, this gives b=−log2 and four weights of 3/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. The full-sort implementation passed regression tests for this case with four zero scores at k=3 and 17 near-zero scores at k=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=2 counterexample, drawing fresh noise means the threshold count C 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: