LapSum – One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection
Łukasz Struski, Michał B. Bednarczyk, Igor T. Podolak, Jacek Tabor · 2025
Read LapSum – One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection by Łukasz Struski, Michał B. Bednarczyk, Igor T. Podolak, Jacek Tabor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06242.txt.
Introduction
Łukasz Struski, Michał Bednarczyk, Igor Podolak, and Jacek Tabor make ranking and sorting steps smooth enough for gradient training. Their paper from twenty twenty-five presents LapSum, a method for soft order tasks. Neural nets need losses that flow through ranks, top-k picks, and permutations. Hard versions of these steps block gradients outright.
The core is a closed form for the inverse of LapSum, a sum of Laplace spreads. That form keeps compute and memory low when picking top values. Losses and gradients run in near-linearithmic time. Wide tests show wins over top rivals, most on high-dimensional inputs and large k. Both CPU and CUDA builds are provided. The authors pitch the method for large-scale ranking jobs where smooth order matters.
Catalog record
| CREATOR | Łukasz Struski, Michał B. Bednarczyk, Igor T. Podolak, Jacek Tabor |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-06242
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LapSum – One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection Łukasz Struski, Michał B. Bednarczyk, Igor T. Podolak, Jacek Tabor Abstract We present a novel technique for constructing differentiable order-type operations, including soft ranking, soft top-k selection, and soft permutations. Our approach leverages an efficient closed-form formula for the inverse of a function LapSum \mathrm{LapSum} , defined as a sum of Laplace distributions. This formulation ensures low computational and memory complexity in selecting the highest activations, enabling losses and gradients to be computed in O ( n log n ) O(n\log{}n) time. Moreover, LapSum \mathrm{LapSum} can easily be parallelized, both with respect to time and memory. Through extensive experiments, we demonstrate that our method outperforms state-of-the-art techniques for high-dimensional vectors and large k k values. Furthermore, we provide efficient implementations for both CPU and CUDA environments, underscoring the practicality and scalability of our method for large-scale ranking and differentiable ordering problems. † † affiliationnotice: Equal contribution 1 Introduction Neural networks are trained using data through gradient descent, which requires models to be differentiable. However, common ordering tasks such as sorting, ranking, or top-k selection are inherently non-differentiable due to their piecewise constant nature. This typically prevents the direct application of gradient descent, which is essential for efficient learning from data. These challenges have become increasingly relevant in recent years ( Lapin et al., 2016 ; Blondel et al., 2020 ; Petersen et al., 2022b ) . To address them, relaxations or approximations are needed to make such tasks compatible with neural network training. This can be achieved by smoothing the objective functions, introducing uncertainty into algorithms, softening constraints, or adding variability. The known methods include smoothed approximations ( Berrada et al., 2018 ; Garcin et al., 2022 ) , optimal based ( Cuturi et al., 2019 ; Xie et al., 2020 ) , permutations ( Petersen et al., 2022b ) . Some of these solutions are often not closed form. Figure 1: Scheme depicting the procedure for calculating the probabilities p_{i} in the soft top-k selection algorithm for \mathrm{LapSum} , given n centers of Laplace distributions r_{i} and a value k<n . All the formulae have a closed form and can be computed, jointly with derivatives, in O(n\log{}n) time and O(n) memory. Challenges in addressing order related tasks arise from several factors. Among them are abrupt changes and instabilities when traversing regions. Time and memory issues often limit the solutions for large n and k values, where the aim lies in computing soft differenitiable top-k for large sequences of size n . There might also issues with scalability, parallel and batch processing. Techniques employed to solve these problems include relaxations and estimators, ranking regularizers, even learning-based ranking solutions. However, some problems remain unsolved or the existing methods are incomplete. E.g., efficiency in terms of time and memory usage may still be inadequate, impeding the solution of certain tasks ( Xie et al., 2020 ) . Frequently, there is a speed-precision trade-off. Several methods lack closed-form solutions, confining one to approximations or complicated calculations. Some methods do not yield probabilities ( Blondel et al., 2020 ) . Several do not yet support easy-to-use GPU methods. Our aim was to address the above-mentioned issues. The main achievement of this paper is the construction of a general theory, based on arbitrary density, such that incorporation of the Laplace distribution provides a closed-form, numerically stable, and efficient solutions to all previously mentioned problems. More precisely, our approach, called \mathrm{LapSum} , is based on a sum of Laplace distributions, see the scheme Fig. 1 for construction of soft top-k selection problem. We show that this approach gives a solution that is both theoretically sound and practical: the reduced O(n\log{}n) time complexity is on par with that of sequence sorting, while the memory requirements are very limited in comparison to other available top-k solutions. As the main contributions of this paper, we • propose a novel, theoretically sound simple closed-form solution, called \mathrm{LapSum} , for all classical soft-order based problems 1 1 1 Our basic top-k solution’s pseudo-code is just 26 lines long (see Appendix A ). , • prove and experimentally verify that \mathrm{LapSum} has O(n\log{}n) low time and O(n) memory complexities, together with derivatives, outperforming within this aspect all other existing methods, see Fig. 2 for comparison with other SOTA methods, • offer easy to use code for \mathrm{LapSum} , for both CPU and CUDA, which makes our approach feasible for large optimization problems thanks to efficient use of parallelization. 2 2 2 Full code is available at github.com/gmum/LapSum . Figure 2: Upper: the relationship between the data dimension n (horizontal axis) and the maximum memory usage and computation time (vertical axis), with k=n/2 in this figure. Computations for forward/backward processes shown here were performed on a CPU (see Appendix Figs. 11 , 13 , 10 and 12 for more). Below: the critical confidence diagram showing the statistical confidence of the above results ( Demšar, 2006 ) . \mathrm{LapSum} approach is comparable to the best few (better on the right, statistically comparable joined with horizontal segments). 2 Related Work The strategy of direct top-k training to optimize network performance, rather than straightforward use of top-1, was first introduced in fast top-k SVM ( Lapin et al., 2016 ) . The proposition called for the construction of differentiable loss functions to enable gradient learning. Several methodologies are available. Some focus on smooth approximations . Berrada et al. (2018) proposed a smooth top-k to more accurately approximate the top-k loss and facilitate a direct technique for top-k gradient learning. Although these and comparable methods for direct gradient-based top-k learning yield precise results, they can be computationally intensive ( Garcin et al., 2022 ) . Some smooth approximations can speed up optimization, but may sacrifice accuracy. Multiple methods employ the theoretically sound optimal transport framework, known for delivering precise gradients ( Cuturi et al., 2019 ; Xie et al., 2020 ; Masud et al., 2023 ) . However, these techniques might become computationally intensive when applied to large-scale tasks. Various studies have expanded on these foundational concepts. Ranking and learning to rank techniques have evolved to deal with large-scale challenges, such as high dimensionality and handling partial derivatives ( Xie et al., 2020 ; Zhou et al., 2021 ) . Significant advances have been made in the proposal of methods that train efficiently with multiple labels through permutation training ( Blondel et al., 2020 ; Petersen et al., 2022a ; Petersen et al., 2022b ; Shvetsova et al., 2023 ) , sorting methods ( Prillo & Eisenschlos, 2020 ; Petersen et al., 2022a ) , and the development and extraction of efficient sparse networks for use in expert systems ( Sander et al., 2023 ) . These approaches aim to improve computational efficiency, scalability, applicability to deep architectures, and effective hardware implementation. Multiple studies demonstrate effective applications of top-k learning techniques in pattern recognition and feature extraction, the creation of sparse networks and feature extraction, and recommender systems, such as through the use of differentiable logic gates ( Zhao et al., 2019 ; Hoefler et al., 2021 ; Chen et al., 2023 ; Xu et al., 2023 ; Chen et al.,