# Fast LapSum: Exact Differentiable Top-k at Million Scale

arXiv: https://arxiv.org/abs/2608.06912 · HTML: https://mlsanity.com/paper/2608.06912/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 34 references that are in the map.
- First posted on arXiv 7 Aug 2026.

## Builds on (most cited first, 24 of 24)

- [3D Gaussian Splatting for Real-Time Radiance Field Rendering](https://mlsanity.com/paper/2308.04079/) (2023)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification](https://mlsanity.com/paper/2106.02034/) (2021)
- [ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders](https://mlsanity.com/paper/2301.00808/) (2023)
- [Scaling and evaluating sparse autoencoders](https://mlsanity.com/paper/2406.04093/) (2024)
- [Movement Pruning: Adaptive Sparsity by Fine-Tuning](https://mlsanity.com/paper/2005.07683/) (2020)
- [k-Sparse Autoencoders](https://mlsanity.com/paper/1312.5663/) (2013)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Sparse and Imperceivable Adversarial Attacks](https://mlsanity.com/paper/1909.05040/) (2019)
- [SparseFool: a few pixels make a big difference](https://mlsanity.com/paper/1811.02248/) (2018)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [SoftSort: A Continuous Relaxation for the argsort Operator](https://mlsanity.com/paper/2006.16038/) (2020)
- [Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision](https://mlsanity.com/paper/2105.04019/) (2021)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Differentiable Top-k Operator with Optimal Transport](https://mlsanity.com/paper/2002.06504/) (2020)
- [LapSum -- One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection](https://mlsanity.com/paper/2503.06242/) (2025)
- [σ-zero: Gradient-based Optimization of ℓ0-norm Adversarial Examples](https://mlsanity.com/paper/2402.01879/) (2024)
- [Sparse-PGD: A Unified Framework for Sparse Adversarial Perturbations Generation](https://mlsanity.com/paper/2405.05075/) (2024)
- [Differentiable Fast Top-K Selection for Large-Scale Recommendation](https://mlsanity.com/paper/2510.11472/) (2025)

## Abstract (arXiv)

Selecting the top-k 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-k 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-k formulation that preserves an exact selection mass of k, 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 106, 107, and 108 scores in median times of 0.92, 1.39, and 7.24 ms, respectively, making exact-budget soft top-k 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-k can be incorporated into practical million-scale optimization pipelines.