A new algorithm lets AI systems pick the exact best k items out of a hundred million in milliseconds, without breaking the smooth math that models need to learn.
Researchers introduced Fast LapSum, a GPU solver for differentiable top-k selection that keeps an exact selection budget of k while remaining fully differentiable. Instead of sorting every score, it uses probabilistic bracketing: it narrows the search to a thin band around the likely cutoff using noised samples, then runs a certification pass to verify the result, falling back to a full sort only in the worst case. The certified GPU implementation processes a million scores in 0.92 milliseconds, ten million in 1.39 milliseconds, and a hundred million in 7.24 milliseconds. The team tested it on two problems: generating sparse adversarial image attacks that perturb only a small fraction of pixels, and trimming the number of 3D Gaussians needed for 3D Gaussian splatting renders.
Top-k selection quietly underpins a lot of large-scale AI infrastructure - deciding which experts to activate in a mixture-of-experts model, which tokens to route, or which attention weights to keep. Picking a hard, countable subset usually breaks the smooth gradients that training depends on, forcing a choice between exactness and trainability. Fast LapSum's pitch is that it removes that tradeoff at the scale where routing and attention pruning actually happen in production models.
On the adversarial-image task, it beat existing state-of-the-art methods by an order of magnitude - a sizable claim for something that is, at its core, sorting with extra steps.