LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection
Authors: Łukasz Struski
Michal B. Bednarczyk
Igor T. Podolak
Jacek Tabor
Venue: ICML 2025 poster (2025)
Keywords: soft top-k selection
soft permutation
soft ranking
differentiable algorithms
Laplace distribution
complexity
Primary area: deep_learning->algorithms

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 the function LapSum, defined as the 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)$ time. Through extensive experiments, we demonstrate that our method outperforms state-of-the-art techniques for high-dimensional vectors and large $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.

LapSum - One Method to Differentiate Them All:
Ranking, Sorting and Top-k Selection
Lukasz Struski!
Michal B. Bednarczyk 12
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 per- mutations. Our approach leverages an efficient closed-form formula for the inverse of a func- tion LapSum, defined as a sum Laplace dis- tributions. This formulation ensures low com- putational and memory complexity in selecting the highest activations, enabling losses and gra- dients to be computed in On logn) time. More- over, LapSum can easily be parallelized, both with respect to time and memory. Through exten- sive experiments, we demonstrate that our method outperforms sate-oof-the-ar techniques for high- dimensional vectors and large l values. Further- more, provide efficient implementations for both CPU and CUDA environments, underscor- ing the practicality and scalability of our method for large-scale ranking and differentiable ordering problems.
+
Pz f dx)
Po
[[x
1o)
P1
n2)
-6
-2
F0 b
Figure I. Scheme depicting the procedure for calculating the prob- abilities in the soft top-k selection algorithm for LapSum, given n centers of Laplace distributions r; and a value < n. All the formulac have closed form and can be computed, jointly with derivatives, in (m log n)) time and O(r) memory.
them, relaxations approximations needed to make such tasks compatible with neural network training. This can be achieved by smoothing the objective functions, intro- ducing uncertainty into algorithms, softening constraints, or adding variability. The known methods include smoothed approximations (Berrada al., 2018; Garcin al., 2022), optimal based (Cuturi al., 2019; Xie et al., 2020), permu- tations (Petersen et al., 2022b). Some of these solutions often not closed form.
1. Introduction
Neural networks are trained using data through gradient descent, which requires models to be differentiable. How- common ordering tasks such sorting, ranking, top-k selection are inherently non-dif non-differentiable due to their piecewise constant nature. This typically prevents the di- rect application of gradient descent, which is essential for efficient learning from data. These challenges have become increasingly relevant recent years (Lapin al., 2016; Blondel et al., 2020; Petersen al., 2022b). To address
Challenges in addressing order related tasks arise from sev- cral factors. Among them are abrupt changes and insta- bilities when traversing regions. Time and memory issues often limit the solutions for large and is values, where the aim lies in computing soft differenitiable top-k for large sequences of size There might also issues with scala- bility, parallel and batch processing. Techniques employed to solve these problems include relaxations and estimators, ranking regularizers, even learning- ranking solutions. However, some problems remain unsolved or the existing methods are incomplete. E.g., efficiency terms of time and memory usage may still be inadequate, impeding the solution of certain tasks (Xie al., 2020). Frequently, there is speed-precision trade-off. Several methods lack closed- form solutions, confining one to approximations or com- plicated calculations. Some methods do not yield proba- bilities (Blondel et al., 2020). Several do not yet support easy-to-use GPU methods.
"qqual contribution 'Fcully of Mathematics and Com- puter Science, Jagiellonian University, Kraków, Poland University of Illinois. Stbana-Champaign USA. Corre- spondence to: Lukasz Struski <lukaszz.truskiee www.ssiiiujj............ Michal B. Bednarczyk <michalb3 illinoos..edu...... Igor Podolak sigor.podolak @ edu.pll, Jacck Tabor rjacc..abrrrjj..du......
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

LapSum: One Method to Differentiate Them All
Our aim was address the above-mentiones issues. The main achievement of this paper is the construction of general theory, based on arbitrary density, such that incor- poration of the Laplace distribution provides a closed-form form, numerically stable, and efficient solutions to all previously mentioned problems. More precisely, our approach, called LapSum, is based on a sum of Laplace distributions, see the scheme Fig. 1 for construction of soft top-k selection prob- lem. We show that this approach gives a solution that is both theoretically sound and practical: the reduced (n log n) time complexity is on par with that of sequence sorting, while the memory requirements are very limited in compari- son to other available top-k solutions.
Batcher 1988 (Bitoncc
Sander (Dyista)
Crover sial, 2018 (NarmBBor))
Sanddr wi wi, (PAV)
Lap-Tope (ours)
Kin at. 2020 (Citima Traneport)
Petorson et al. (Spitter Selection)
Forword Backward
Runlma
10"
Memory (CB)
10
10"
16*
10'
10'
10"
16"
10"
10
Dimensions
Citicall differance diagram
0.8
As the main contributions of this paper, we
propose a novel, theoretically sound simple closed- form solution, called LapSum, for all classical soft- order based problems',
Petersen [0.14]
[1.00] Lap-lop-k (ours)
Batcher [0.30]
10.68 Xie
[Dykstra) [0
(2,02) Sander (PAV)
[0.44] Grover
prove and experimentally verify that LapSum has (n log n) low time and (nn) memory complexities, together with derivatives, outperforming within this aspect all other existing methods, see Fig. for com- parison with other SOTA methods,
the relationship between the data dimension n (horizontal axis) and the maximum memory usage and computation time (vertical axis), with & = n/2 in this figure. Computations for forward/backward processes shown here were performed on CPU (see Appendix Figs. 10 to 13 for more). Below: the critical confidence diagram showing the statistical confidence of the above results (Demšar, 2006). LapSum approach is comparable to the best few (better on the right, statistically comparable joined with horizontal segments).
Figure 2. Upper:
offer easy to use code for LapSum, for both CPU and CUDA, which makes our approach feasible for large optimization problems thanks to efficient use of parallclization.?
2. Related Work
Various studies have expanded on these foundational con- cepts. Ranking and learning to rank techniques have evolved 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:b; 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.
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 smooth top-k to more accurately approximate the top-k loss and facilitate direct technique for top-k gradient learning. Al- though these and comparable methods for direct gradient- based top-k learning yield precise results, they can be com- putationally intensive (Garcin et al., 2022). Some smooth approximations can speed up optimization, but may sacrifice accuracy.
Multiple studies demonstrate effective applications of top-k learning techniques in pattern recognition and feature extrac- tion, the creation of sparse networks and feature extraction, and recommender systems, such through the use of differ- entiable logic gates (Zhao et al., 2019; Hoefler et al., 2021; Chen et al., 2023; Xu et al., 2023; Chen et al., 2021).
Multiple methods employ the theoretically sound optimal transport framework, known for delivering precise gradi- ents (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.
Theoretical studies establish links between top-k learning and classical statistical learning, the margin methodology, and a broader framework, offering strategies to optimize the
Our basic top-k solution's pseudo-code is just 26 lines long (see Appendix A). Full code is available at githuh.com/gmum/lapSSi
2

---

LapSum: One Method to Differentiate Them All
k value Cortes et al. (2024); Mao et al. (2024).
Then we have
8 dr
(r, (a(
(1)
3. General soft-order theory based on sums of cumulative density functions
Now we compute the derivatives of the inverse function k - F-Sum (r, k). Given & E nO, let b = (r k)
We begin by demonstrating how cumulative density func- tion be used construct soft analogues of hard, order- based problems such as top-k selection and permutations. Although the proposed approach is primarily theoretical and not computationally efficient for a general density, in the next section we show that it can be efficiently computed with complexity (n logn) in the specific case of the Laplace distribution.
denote the unique solution to
F-Sum(b) = Fa =
To compute the derivative of the function with respect to w, we differentiate the above formula with respect to obtaining 0k E, fa - rz)) = 1. Thus
0b
Fum,
i Ōk
Øb
1
(2)
3.1. Function F-Sum
ak
E.fa(b r4)
We base our construction on an arbitrary even and strictly positive density function f. with F denoting its cumulative density function, that F--x) quently F(O) 1/2. Additionally, for scale parameter * 0 we put
3.2. Soft rankings and soft orderings
F(x) and conse-
We show how F-Sun may be applied to provide solutions to differentiable soft order problems. Let us start with the soft rankings problem.
Fa(x)= = (
z
Observe that (x) + (x)) as a + 0+, where H denotes the Heaviside step function, with (0))= 1.2 and (x) - H-=x) as a 0
a 0.1
Given sequence (ro. (ro...., In-1) R, consider the function
F-Suma x) = Fa(x= (a((--r)..
Figure 3. The computation of the soft ranking based on F given as CDF of Laplace distribution, here 81, F- F-Ranka=1(Po, r2,
Clearly, the image of F-Sum, is the interval (0, It occurs that F-Sum, is invertible as function of x. This follows from the fact that since f is strietly positive density, Fa is a strictly increasing continuous function for > and strictly decreasing for a < O. Consequently, F-Sum, (z, r) is a continuous strictly monotonous function, which is concluded in the following observation.
Soft rankings For a of 0, fixed sequence (r;) and an arbitrary j E (O...., n- 1} we define
F-Ranka F-Suma ry)
see Fig. 3. By a soft ranking of whole sequence r = (rr) we understand
Observation 3.1. Let sequence r = (ro...., In-1) E R be given, and let lo E (0,n), a + 0 be arbitrary. Then the equation
F-Ranka (r) = (F-Ranka (ri))
First, we show that F-Rank, (r,) n0 This follows directly from the formula
F-Suma(r,at k
has unique solution x, which we denote by F-Sum-1(
F- F-Ranka(r,)
Σ Falry -r).
(3)
which is consequence of the equality Fa(r, r.)) ((0)=1)
should be noted, that in our reasoning we do not require to be integer.
One can easily observe that F-Rank, is permutation- equivariant, that is, a permutation of the input will result in similar permutation of the output. By s we denote the rank of r, in sequence (with respect to standard order), i...
Derivatives Note that the above functions are differen- tiable and that the derivatives can be computed efficiently. By fa we denote the function fa (z) = 1 a fz/a). Observe that, for a > O, it is the density whose CDF is equal to F..
8 card(j :, < <rr) Σ H(r (11r-11) (r))-
3

---

(rTopa - max, (r) as 0 LapSum: One Method to Differentiate Them All
With oj denote the rank of element r; in the reverse order of r, that is, 8 (n 1) s.- To prove that F-Rank, is correct soft version of ranking operation, we need to show that in the limiting case a + 0= we obtain the hard ranking.
3.3. Soft top-k
We proceed the construction of soft differentiable version of top-k selection problem. The aim is to construct dif- ferentiable version of the hard top-k (formally max top-k) operation which, for sequence = (r:) E R" returns binary sequence (p:) E {0, 1 that has value 1 for the indices with k highest values of r, and zero for all other indices. Clearly, >; k.
Theorem 3.2. For a sequence r (ri) of pairwise distinct elements we have
F-Ranka (r²) + 5f as a -
for arbitrary E (0,...,n--1.. 11
In our approach, we choose arbitrary k E (0, where underline that we do not require & to be inte- ger. Using F'Suum construct the parameterization of the space
Proof. Let us prove the limiting formula above for a > 0 (the case < 0 is similar), Since Fa, for + 0 converges to a Heaviside function, by (3) we get
A = -_PP......P...... .P. E (0, Σ =k].
lim F-Ranka (r)) = lim a-30+
Σ (r - rs)
Formally, we define
a-0
F-Top, (r, k) (Fa ro)........ Fa (b rn-1))
Σ H(r r;) = =s--
where = P-Sum (r, (r,AH k),
see Fig. for visualization this approach.
We show that this gives us the correct solution for the soft top-k problem.
Thus, with a - 0+, we obtain the hard ranking of the sequence in increasing order, while for a + 0 obtain the ranking in decreasing order.
Theorem 3.3. For every E (0, n)) and r E IR" we have
F-Topa (r; , k) E Ak-
(4)
Soft orderings Soft ordering can be intuitively seen an inverse operator to soft ranking. Given a sequence (rs) we define
Moreover, if k is integer and the elements of r are pairwise distinct, then
F- k) top ming (r) as 0+,
(F-Sorta (r)); F-Sum +1) for {O....,m-
Informally we can write
(r) F-Sum,," (1 (0, 10.1,...,, 1))
Proof. Observe that (4) follows directly from the fact that F-Sum (r, k). and thus Σ, Fa (b -r;)- ) = k.
can now be readily demonstrated that for a sequence r with distinct clements, the affreementooned operation has the following properties, see Fig.
Due the limited space, the proof of the limiting case is given in the Appendix Theorem B.
it is permutation invariant,
Invertibility of F-Sum One can observe that the func- tion F-Top has properties similar to that of softmax. In particular, two outputs are equal, then the inputs are equal modulo some constant translation. Namely, by the invertibil- ity of F' obtain that if F-Top, then
(-Sorta(r) converges to the sorted (with respect to increasing order) r for a + 0+,
(-Sorta(r) converges to sorted (with respect to de- creasing order) + 07.
F-Top, (F, k)
F; = + (b- b) for every where b = F-Summ1 (r, k)), = F-Sum implies, in particular, that similarly to softmax, F-Top,, with domain restricted {r (rx) E R² E. T. = 0} is invertible.
2.5
0.1
-1 (F, k). This
5
35
fg 9)
Fg O2
Figure The result sorting with given by CD Laplace distribution. Observe that for small the constructed sequence (go. Zt 92) F-Sorta=1(Po, T2) practically coincides with the sorted sequence
3.4. Soft permutations
The task of the soft permutation problem is to generalize the hard permutation matrix to a differentiable double stochastic

---

Recall that the permutation matrix corresponding to a per- mutation (s1))=1..n of the indices (l,...,r) n)) square binary matrix that represents the reordering of elements LapSum: One Method to Differentiate Them All
Theorem 3.6. Let IR be arbitrary and let O. Then
F-Perma (r) E Bn.
ubg
Moreover, ifr has pairwise distinct elements, then
(bo.
11
F-Perma (r) + permolaation permulaaion_maaria((") as a - 0+.
F0x
dx
P12
J.
by
Proof. We prove that F-Perm, (r) is doubly stochastic. Let an arbitrary j E {O...., 1}. Then
Figure 5. Illustration of probability calculation for sort/permutation method. We show the underlying processes generating proba- bilities under given conditions.
(Fa (Fa(bi+ - -ry) - Fa r;))
Fa((o) Fa(000) = 1. Now fix arbitrary E 10, ,0,..., 1}. Then
matrix.
(Fa - r - Fab - -r)))
in the sequence. Preciscly, the permutation matrix P is matrix x where:
F-Sum(r, bb+1) (aiii)F-SSumffe
F-Sum(r, by) (j+1)-j--
The proof of the limiting case + 0 can be done similarly to the reasoning from Theorem B.1 in the Appendix.
each row and column contains exactly one entry of 1, and all other entries are 0,
if P is applied to vector v, the result is a reordering of v according to (si).
4. Theory behind LapSum
In the previous section we have constructed general soft- order theory based on an arbitrary cumulative density func- tion F. However, such an approach is in practice unapplica- ble, since the complexity of evaluating F-Sum (r, x)) for a sequence of size is in general quadratic. Moreover, to efficiently apply the theory, we need to able to compute the inverse function F-Sum (r, w). Finally, use the model for neural networks, would optimally need the derivatives computed in complexity O log
To construct P. first create a zero matrix n X n, and then, for each i E {1, (1. n), place a in the (i. p:)- position.
Example 3.4. Let (x:) = (3, 1,.). The permulation matrix 10011
is: P 100
1010
For sequence (r:) of pairwise distinct scalars, by its (hard) permutation matrix, we understand the permutation matrix of (s:). where is the rank order of r; in the ordered r.
By B, we denote the space of all doubly stochastic matrices of size n x n, where we recall that a doubly stochastic matrix a square matrix of non-ne negativve real numbers where each row and each column sum up
4.1. Where the magic happens...
We demonstrate that all the above mentioned problems can be solved when F represents the CDF of the standard Laplace distribution given by
Soft permutation task The aim of soft permutation task to define a differentiable function P: R" > Maxn. so that Prr) E B, for E R= and that hard permutation can be obtained as a limiting case soft permutation. We consider only O.
2 (x)
for S 0, for x >> 0.
Lap(x) 1 1 exp(-x)
The crucial role in our experiments will be played by the function Lap-Sum, which is the sum of the Laplace cumulative density functions. Recall that for sequence = (r:)i=o..n-1 C RR applying the definition for F-Sum for F = Lap we get
Definition 3.5. Given r = (ro...., In-1) E _2" and a we define
F-Perm,, = [F. (b:41 TTy)= - F., - -y)liss where b-1 00, b, F-)(i) for O...., bn 00.
Lap-Sum,
Σ Lapa(x rz),
where Lapa(x) = Lap(x/a).
Visualization of the definition is given in Fig. 5. We proceed theorem, which gives justification of the defined function.
The function Lap-Sum will crucial in solving all previ-
5

---

LapSum: One Method to Differentiate Them All
ously mentioned soft-order problems we shall denote the family of methods constructed with the use of Lap-Sum function as LapSum. We show two crucial facts which enable the efficient use of LapSum in soft-order problems:
compute the sequences 0gy c cj in complexity (n)). Now in complexity O(n+ m) we find n, for 1 = 0, o
such that æ [mm "/n=11,nm) Finally, thanks to the proposi- tion, we obtain Lap-Sum, (2)) is given by
we can evaluate Lap-Sum at n points in complexity
2 exp( (xp("")))) f exp( "ssp(==")= cj+11
(n log nt).
which directly implies that we can compute all these values in O(n + m) complexity.
the computation of Lap-Sum can be parallelized,
the function Lap-Sum has inverse given by closed- form formula.
Parallelization Observe that the iterative formulas for dg by and can be computed in parallel by applying the standard prefix scan approach.
Theorem 4.1. Suppose that r (rs)i=u..n- n-1 C I is in-
creasing sequence. We can compute the values of Lap-Sum for an increasing sequence x = (1,))=o0mm- C I with a complexity of O + m).
Calculation of inverse function We now show that function (0, n)
To prove this theorem, we will need the following proposi- tion.
- Lap-Sum, (r, k) can be com- puted with simple straightforward formula. For clarity, present the formulae for a 1.
Proposition 4.2. Assume that (ra)s=0..n11 is an increasing sequence and a > O, where we additionally put r-1 Tn = 0o.
First compute w; = Lap-Sum(rr) for all i = 0.. 1. If & E (-oc, rol. then as on this interval Lap-Sum(1) = so exp(x - ro), solution to Lap-Sum = is given by 2
Then
Lap-Sum(x)=
== ro + log 2 + log w log do
= = exp
x- x-1/+1
1- + +g++1 f0zt1 exp
If E [ri-1, ry] for some 0 < < n then, since Lap-Sum(x) 2 exp(x-Tj+1 r
for x E [r,, ryt1lis 11.(n 1).
(5) and
- -bbbt1 exp(r; - x)) + cj+1, by direct calculations, the solution for Lap-Sum(( = is I Tj+1 log aj+
where sequences (a:)i=-1.nn (bi)i=a.n c R (4)i=o.. C N are defined iteratively by the formulae
aN-1 = 0, a = expl [h 1=) (1+aa)
+ +log(k Cj+1 + v - cyt1l + a,bjt1 e ((+)))+)).
bn= = 0, bi+1 = exp(" (+ b₁).
If l: [rn, 00), we analogously compute
co 0, c/+1 = 1 + Cj.
r = Tn-1 - log 2 - log((c, k) + log bn.
Proof. Given that F on the intervals (-o0, 0] and oo) is composed of constants, exp(x/o), and exp(-x/ax). this property extends to function Lap-Sum,(E;;) for every interval 11. Consequently, there exist sequences aj. bj. Cj that satisfy formula (5). We aim to demonstrate that the proposition's 's recurrent formulas are valid.
4.2. Efficient computation of derivatives
The fascinating aspect of the functions being analyzed is our ability to calculate all required derivatives in O(n log n) time. The key to this efficiency is that instead of comput- ing derivatives in matrix form, we construct formulas for right and left multiplication of the derivative by row and column vectors, respectively. A more detailed explanation is provided in the Appendix.
Consider the interval (-oo, ro). Clearly, co is zero because the expression for Lap-Sum in this range is composed of exponentials. Assuming that the expression for cy holds, it follows that in the next interval, we increase by 1. This logic is uniformly applied to all subsequent Cj. Now, consider the sequence ay. Initially, note that an-1 = 0. Using a similar reasoning, we derive the entire recursive formula.
Let us start with the case of top-k selection, namely for function Lap-Top,,.C (r, k). Define the function P : R
= (rx) - = (p:) E A C [0, 1]m, where
P: Lapa r2) where Lap-Sum, (r,k).
We are now ready to present the proof of Theorem 4.1.
It can be shown (see Appendix C.2), that the derivative of with respect to r is given by the matrix
Proof of Theorem 4.1. Since the sequence (ra)i=o.nn-1 is ordered, then, according the above proposition, we can
OP = s diag(s),
(6)
Ow
'The case for a < O can he treated analogously.
where = =s:) E R. is given by s; = a min(ps, 1 p:)
6

---

LapSum: One Method to Differentiate Them All
and
Table I. Performance comparison of permutation- methods on CIFAR- 110R-1000RR using ResNet18. The table shows ACC@1 (standard accuracy) and ACO@5 (top-5 accuracy). Bold and italic values denote the best and second-best results, respectively. P3 represents the training probability distribution, Methods marked with (*) are based on Berrada et al. (2018).
softmax
b-
TM
For optimizing purposes, utilizzig such a constructed deriva- tive would result in complexity of at least O(n²). However, note that to apply gradient optimization it is actually enough to compute o² D and D for an arbitrary vector c. By exe- cuting direct calculations, one can trivially derive from (6) the formulae
CIFAR-100
Method
P3
ACC@1
ACC@5
Smooth top-
[0.,0.0.00.1I]]
53.07
85.23
De = (g, v) 8- -8 O v, and 0. DTD (s) U",
NeuralSort
[0.00.0.0.11]
22.58
84.41
where denotes component-wise multiplication.
SoftSort
[0.00.0.0.11]]
01.01
05.09
SinkhomSort
[0.00.0.00,111]]
55.62
87.04
Another important function, necessary to calculate soft- sorting and permutations is, for fixed & S n, the function
DiffSortNets
[0,,0.,0,00,111]
52.81
84.21
Lap-Top-k (ours)
10.00,0,00,11]
58.07
87.50
NeuralSort
2.2.2,22,2.221
61.46
86.03
L(r, kn...., ......,kjj) kj-1) = (Lap-Summ"((t (a.ph))...,,a-SSSunn Lup-Suma" (r.
SoftSort
[22.2.22,2.21
61.53
82.39
SinkhornSort
[22.22.2,.2222
61.89
86,94
DifsSortNets
[22.2.2.2,22
62.00
86.73
In this instance, calculating the derivative of L efficiently, in particular the left and right multiplication of the deriva- tive by row and column vectors, respectively, can also be implemented within time complexity of (n l).
Lap-Top-k (ours)
[22,2,22.2.22 64.53
88.51
perior results faster due to LapSun's efficient time and memory management in handling this intricate task. The re- sults of ImageNet-IK IK are on par with those of other methods. This demonstrates that LapSum is particularly well suited for high-dimensional tasks, being fast and easy to use for other tasks. At the same time, LapSum has a differentiable parameter a (see Sec. 3.1), which can be used to fine-tune individual solutions. The results of these experiments presented in Appendix D).
5. Experiments and results
The main incentive of this paper was to design new and simple to implement closed-form method that would con- stitute tool for use in all the order tasks. We wanted LapSum to outperform other methods in terms of time and memory complexity, while obtaining the general SOTA in the standard experiments.
Petersen et al. (2022b) algorithm suggests a predetermined number of m best results to compute for differential ranking. This increases its effectiveness.
5.1. Experiments on soft-top-k methods
Our evaluation consists of training from scratch on CIFAR- 100 and fine-tuning on ImageNet-16 K and ImageNet-21K-PP datasets. These evaluations aim to assess LapSum's 's in- fluence of t and top-5 training on accuracy metrics. The experiment highlights the effect of the smaller number of classes in CIFAR-100 compared the larger count of 1000 in ImageNet-IK and an even greater count of 10450 in MingeNet-21K-PP We employ Pj settings akin to those in Petersen et al. (2022b). Experiment details are available in Appendix D.
Runtime, and memory analysis Fig. 2 depicts the experimental time-memory correlations for LapSum along- side other algorithms. We exclude (Blondel et al., 2020) as it does not return probability vectors (Petersen et al., 2022b); we also exclude (Prillo & Eisenschlos, 2020) as we found their method not working for some random input data. The relationships of time/memory against data dimension and k with k n/2,, is considered. It is evident that, concerning memory usage, LapSum (the blue solid line) outperforms, or at least matches, the best competing approaches, in par- ticular for higher data dimensions. Some algorithms could not complete tasks due to memory limitations. Similarly, this holds for time complexity as well. These patterns are consistent for both the standalone forward pass and the com- bined forward and backward passes, using either CPU GPU (see also Figs. 10 to 13 in the Appendix). To assess the statistical significance of these experimental compar- isons, we have performed a critical difference CD ranking test (Demšar, 2006), see Fig. 2, which shows that LapSum outperforms other competitive algorithms.
Refer to Tab. 1 for the CIFAR-100 results, where we used P3 = [0., 0., 0., 0., 1.] for top-5 learning. Furthermore, we used [.2, 2, 2, 2, 2] have direct comparison with the results given in Petersen et al. (2022b). Our experiments demonstrated superior or at least comparable results. The results are consistently stable and are fast to obtain.
Tab. 2 summarizes the outcomes of fine-tuning on ImageNet- IK and ImageNet-2IK-P. similarly to the setup in Petersen et al. (2022b). The ImageNet-211 results show LapSum surpass alternative methods. LapSum yields slightly su-

---

LapSum: One Method to Differentiate Them All
Table Results on ImageNet-1K IK and ImageNet-21K for fine- tuning the head of ResNeXt-101 (Mahajan et al., 2018). We report ACO@1 and ACOW5 accuracy metrics, averaged over seeds for ImageNet-1K K and 2 seeds for ImageNet-21K-P. Methods are evaluated using different P3 configurations, highlighting effec- tiveness in optimizing ranking- baann losses. Best performances are in bold, with second best in italics. Methods labeled with (*)
Table 3. Accuracy kNN-based methods on MNIST and CIFAR- 10 comparing standard ANN with enhanced variants. Bold and italic values stand for best and second-best results. Our proposed
LNN+Lap-Top- shows strong performance, especially on CIFAR- 10, showing the benefits of Laplacian kaplacian-based based top-k optimization.
Algorithm
MNIST
CIFAR 10
KNN
97.2
35.4
are based Berrada al. (2018).
ANN+PCA
97.6
40.9
Method
P3
Im
ImgNet-21K-P
ANN+AE
97.6
44.2
ACC@5
ACC@1
ACO85
KNN+pretrained CNN
98.4
91.1
RelaxSubSample
99.3
90.1
Smooth top-k"
[0.,0.0.0.1]]
85.15
97.54
34.03
65.56
kNN+NcuralSort
99.5
90.7
NeuralSort
[0,,0,0,0,1.]
33.37
94.75
15.87
33.81
ANN+OT
99.0
84.8
SoftSort
[0.,0.0.0..]
18.23
94.97
33.61
69.82
KNN+Softmax & times
99.3
92.2
SinkhornSort
[0.
85.65
98.00
36.93
69.80
CE+CNN
99.0
91.3
DiffSortNets
[0.,0.0.0.1I]
69.05
97.39
35.96
69.76
&NN+SOFT Top-k
99.4
92.6
I Lap-Top-k (our)
[0.,0,0,0,11]
85.47
97.83
37.93
70.67
ANN+Lap-Topp (ours)
99.4
92.2
NeuralSort
[.5.0.0.0.55]
86.30
97.90
37.85
68.08
SoftSort
[.5.0.0.0.55]
86.26
97.96
39.93
70.63
SinkhornSort
1.5,0,0,0.55
86.29
97.97
39.85
70.56
Batcher, 1968 (Bileni)
Bander al. 2029 (Dylstra)
Grover ol ai, 2019 (NunntBorr)
Sander wt 2023 (FWV)
DiffSortNets
1.5,0,0,0.55]
86.24
97.94
40.22
70.88
Lig- Topik jours)
Xia ol 2020 (Oplimal Transpot))
(our)
1.5,0,0,0,55]
86.28
97.93
40.48
71.05
(Spkiter
(ror
10
10"
0.85
10"
Ent
10
Ficzen
100001
Traissiee [2001)]
10'
10
10"
Dimensoons
5000 11000
-100
-10
0.1
5000 -1000
-10
-10
41
Figure 6. LapSum top-1 and top-5 accuracies across varying val- ues a and top-5 training on CIFAR-100. Higher produces more discrete selections, lower lead to smoother outputs, influ- encing how strictly the model enforces a top-k criterion.
Figure 7. The ertor calculated as Error(k) = Σx= Pi kij where Pt. as function of k (the value defining Top-k the respective methods) and n (the data dimension). The plots correspond to the errors obtained in the computations presented Fig. 2.
5.2. Experiments on noft-permutation methods
Fig. 6 shows the impact of LapSum a trainable parameter value on training on the resulting in harder softer solu- tions (see Appendix D, Fig. 8). We have also performed experiments on the accuracy of direct approximations of k value using LapSum, see Fig. 7. Our proposition con- sistently gives better approximations than competing ap- proaches, irrespective of given problem dimension.
To assess the effectiveness of pettueemttttion techniques techniques, we
enhanced version of the MNIST dataset, the large-MNIST (Grover et al., 2019) where four random MNIST digits are combined into one composite im- age representing four-digits number. This allows to evaluate the techniques' ability to learn correct permutations.
Baseline methods employ a common to all CNN to encode images into a feature space. The row-stochastic baseline combine CNN features into vector processed by multi- layer perceptron for multiclass predictions. Sinkhorn and Gunbel-Sinkhom approaches use the Sinkhorn operator to create doubly-stochastic matrices from these features. NeuralSort- methods apply the NeuralSort operator with Gumbel noise to produce unimodal row-stochastic matrices. The loss in all methods the row-wise cross-
K-NN for Image Classification The protocol followed was adapted from (Xie et al., 2020).4 Tab. shows test accuracies on MNIST and CIFAR-10. 10. We see that Lap-top- does not deteriorate the model performance. We provide additional details Appendix D.
We use the code kindly made available hy authors.
8

---

LapSum: One Method to Differentiate Them All
by Lukasz Struski) and 202349/BB/S6/0111 (work by Jacek Tabor). Some experiments were performed servers purchased with funds from the flagship project entitled "Ar- tificial Intelligence Computing Center Core Facility" from the WigiWorld Priority Research Area within the Excellence Initiative Research University program at Jagiellonian University Kraków.
Table Mean permutation accuracy (%) testset for Large- MNIST for different number of randomly sampled images n. First value is the fraction of permutations correctly identified, while the one in parentheses is the fraction of individual element ranks cor- rectly predicted. Results for competing methods are from Grover al. (2019). Bold and italic values stand for best and second- best results. GumbelS stands for Gumbel-Sinkhorn method, DNeural for deterministic NeuralSort, SNeural for Stochastic NeuralSort.
Method
=
n=5
n=
15
References
Vanilla 46.7 (80.1)
9.3 (60.3)
0.9 (49.2)
(11.3)
0.0 (6.7)
Sinkhom 46.2 (56.1) 3.8 (29.3)
0.1 (19.7)
0.0 (14.3)
0.0 (7.8)
Berrada, L.,, Zisserman, A., and Kumar, M. P. Smooth loss
GumbelS 48.4 (57.5)
3.3 (29.5)
0.1 (18.9) 0.0 (14.6) 0.0 (7.8)
functions for deep top-k classification. arXiv:1802.0755 2018.
DNeural 93.0 (95.7)
83.7 (92.7) 73.8 (90.9) 64.9 (89.6)
38.6 (85.7)
SNeural 92.7 (95.0) 83.5 (92.6)
74,1 (90.9) 64.6 (89.5)
41.8 (86.2)
Lap(ours) 94.2 (96.1) 85.3 (93.2)
74.1 (90.7) 63.1 (88.6)
33.9 (82.4)
Blondel, M., Teboul, O., Berthet, Q., and Djolonga, J. Fast
differentiable sorting and ranking. International Confer- ence Machine Learning. 2020.
entropy against ground-truth permutation matrices with row- stochastic outputs. In our method LapSun we apply the same backbone architecture while eliminating the need for additional layers to transform the stochastic matrix. Tab. 4 provides results of this approach against other methods.
Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, E., and Chi, E. Top-k off off-policy correction for a reinforce recommender system. arXiv: /8 /8/2.0235, 2021.
Chen, X., Li, H., Li, M., and Pan, J. Learning sparse trans- former network for effective image deraining. IEEE/CVF Conference on Computer Vision and Pattern Recognition, June 2023.
6. Conclusions
We have introduced LapSum, new method that enhances the process of performing tasks such as ranking, sorting, and selecting the top-k elements from a dataset. It is straightfor- ward theoretically, can be used for all soft-order tasks, and differentiable with respect to all parameters. LapSum utilizes the properties of the Laplace distribution to improve both the speed and memory usage compared to other exist- ing techniques. The effectiveness of the method has been supported by theoretical and experimental validation. Fur- thermore, we have attached an open source code for this approach, both in Python and in CUDA for execution on GPUs, making it accessible for broader community.
Cortes, C., Mao, A., Mohri, C., Mohri, M., and Zhong, Y. Cardimality set prediction and top-k classification. arXhv:2407.071400 2024.
Cuturi, M., Teboul, O., and Vert, J.-P. Differentiable ranking and sorting using optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
Demšar, J. Statistical comparisons of classifiers over multi- ple data sets. Journal of Machine Learning Research, 7, 2006.
Garcin, C., Servajean, M., Joly, A., and Salmon, J. Stochas- tic smoothing of the top-k calibrated hinge loss for deep imbalanced classification. arXiv:2022.02.193 2022.
Impaet Statement
LapSum enables applications of soft ordering methods to large-scale real-world datasets. Consequently, LapSum has the potential to significantly impact industries relying on scage data processing, such as recommendation systems, natural language processing, and computer vision.
Grover, A., Wang. E., Zweig, A., and Ermon, S. Stochastic optimization of sorting networks via continuous relax- ations. International Conference on Leurning Represen- tations, 2019.
Acknowledgments
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. IEEE Conference on Computer Vision and Pattern Recognition, 2016.
This research was partially funded by the National Science
Centre, Poland, grants no. 2020/39/D/ST/01133 (work
Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., and Peste, A. Sparsity in deep learning: pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 23, 2021.
'In LapSum, logits are fed into modified cross- coos-eytropyy func- tion to align the CNN's output vector with the ground-truth permu- tation vector, reducing complexity while maintaining competitive performance.

---

LapSum: One Method to Differentiate Them All
Kingma, D. P. and Ba, J. Adam: A method for stochas- tic optimization. International Conference Learning Representations, 2015, S.LI::1412.6999
Lapin, M., Hein, M., and Schiele, Loss functions for top-k error: Analysis and insights. arXiv:1512.00486, 2016.
Mahajan, D., Girshick, R. B., Ramanathan, V., He, K., Paluri, M., Li, Y., Bharambe, A., and van der Maaten, L. Exploring the limits of weakly supervised pretraining. European Conference on Computer Vision, 1100, 2018.
Mao, A., Mohri, M., and Zhong, Top-k classification and cardinality-aware prediction. 2403. 19625, 2024.
Masud, S. B., Werenski, M., Murphy, J. M., and Aeron, S. Multivariate soft rank via entropy-regularized optimal transport: Sample efficiency and generative modeling.
Journal of Machine Learning Research, 24, 2023.
Petersen, F. Borgelt, C., Kuehne, H., and Deussen, O. Monotonic differentiable sorting networks. arXiv:2203.09630 2022a.
Petersen, F., Kuehne, H., Borgelt, C., and Deussen, O. Dif- ferentiable top-k classification learning. International Conference on Machine Learning, 2022b.
Prillo, and Eisenschlos, Softsort: A continuous relax- ation for the argsort operator. International Conference on Machine Learning. 2020.
Sander, M. F., Puigcerver, J., Djolonga, J., Peyré, G., and Blondel, M. Fast, differentiable and sparse top-k: convex analysis perspective. International Conference Machine Learning, 2023.
Shvetsova, N., Petersen, F., Kukleva, A., Schiele, B., and Kuchne, H. Learning by sorting: Self-supervised learn- ing with group ordering constraints. /EEE International Conference Computer Vision, 2023.
Xie, Y., Dai, H., Chen, M., Dai, B., Zhao, T., Zha, H., Wei, W., and Pfister, T. Differentiable top-k operator with optimal transport. 2020.
Xu, I.., Wang, R., Nie, F., and Li, X. Efficient top-k fea- ture selection using coordinate descent method. AAAI Conference on Artificial Inteligence, 37, 2023.
Zhao, G., Lin, J., Zhang, Z., Ren, X., Su, Q., and Sun, X. Explicit sparse transformer: Concentrated attention through explicit selection. arXiv:1812.02353,, 2019.
Zhou, T., Liu, J., and Yang, J. Learning with noisy labels via sparse regularization. IEEE/CVF International Con- ference on Computer Vision, 2021.
10

---

LapSum: One Method to Differentiate Them All
A. LapSum: pseudocode for solution of top-k problem
B. Limiting case
Theorem B.1. For every k E (0, n) and r E R" we have
We present the complete pseudocode for the solution of top-w problem constructed in the framework of LapSum. For sequence 8 = (8.))=0..n-1 we construct a sequence = (p:) E (0,1)" 1)", such that
F-Top (r, k) E AR.
(7)
Moreover, if k is integer and the elements of are pairwise distinct, then
Σp:=k
(r k) top (r) as a +t, (r, top (r) as 0...
and the operation > p is differentiable. In the limiting case when the pairwise differences between elements of the sequence are large, the solution tends to hard solution to top-k problem.
Proof. Observe that (7) follows directly from the fact that b F-Sum, (r, k). and thus Σ: Fa (b -r;) k.
We proceed to the proof of the limiting case, where consider the case - 0+ (the case + 0 can be shown analogously). Since the function F-Sum, is equiv- ariant, without loss of generality we can assume that the sequence (rr) is strictly increasing. Consider the values li F-Sum (r, k)). We show that
We put
= { 1 exp(x)
for x S O, cxp(-x) otherwise.
Tap(x)
(ba -ry) + 0 as - 0+.
(8)
Algorithm 1 LapSum: soft top-k function for the input s = (8:)==0.m-11
If this were not the case then, trivially, there would exist a sequence am - 0+ and
such that
Require: Sequence (8x (8:) n-1, parameter (0,
1: Sort s in decreasing into r = (r:)i=0.nn-1
F (Dam - -ry) = F No... ("=_a-" 2 E for all m.
2: Set = 00, I' -00
a
3: Initialize: an-1 = 0, bn = 0, co- = 1 4: for j = n to do
By continuity and fact that F is strictly increasing, this implies that dam -1 > = (=). Consequently for < ks since r. r; > 0, we would get
5: aj-1 = (1 + 03) exp(r; 1
6: end for
7: for j = 0
do
F Fam. (bam - rs)) == Dam -r
F
Dam -r
Ty-Y' Ck.
8: bj+1 = (1 + bj] exp(Ti+1 - T3)
Om
9: Cj+1 = 1+ Cj.
c
c
ri-Te
1 as 171 +
10: end for
which would lead to the inequality
11: Set w= = 0, Wi = n
12: for j = 0 to n do
wyy 2aa exy(px+1111 T3) 1bzt1 + c/+1
lim
Fam (bam rs))
Fay (bar (aa.aaaammmm rry) k
14: end for
15: Find E (O...., n such that h E [wy-1. wy]
This we have obtained a contradiction with the equality
16: if 0 then
E Fa r.) k. This proves the assertion, since we
17: 6 b= ro log 2- - log h + log
trivially obtain that F. F. (b- r3) 0 for a + 0+ and j > k. Consequently, making use of equality Σ Fa ra) k
18: else if 0 < j < n then
b b-r + log aj
we obtain that F. -r;) + for + 0+ and j < k.
19:
llog
k i-c + V bk: 1i--c+112 - -abb==--
C. Calculation of derivatives
20: else if k then
21:
= Tn-1 + log 2 + log(cn. - kb) -log bn
In this section we are going to obtain main formulas for derivatives. We show, in particular, that all derivatives can be easily directly computed. Moreover, what is important for the gradient optimization process the multiplication of all the derivatives on a vector can be computed in O(n log n) time.
22: end if
23: for i 0 to n do
24: P: Lap( 8; b)
25: end for
26: return (p:)
We shall start with establishing some consistent notation.
We are given (ri)==0.n-11 R., k E (0, n) and a # 0.

---

LapSum: One Method to Differentiate Them All
We consider the function
Partial derivatives of Lap-Sum" -1 with respect Differentiating (9) with respect to ri, we obtain:
b b(r, k a)) Lap-Sum (r, k; a))
(
Ob
which by definition satisfies the condition
Σ Lopa(((r, k))
1) O,
ar:
Σ Lapa (b- rı) k,
(9)
and consequently:
where
Ōb
(b(r, r3)) lap, (b(r, k)) rz),
(apa(x)= 1/2 exp(x//a) 1 2 exp(p (=p()
if x/ S O, if x 0.
Ör;
which simplifies to:
We additionally consider the function
Öb
lapa (b(r, k:) rr;)
Σ cappa((rr) k:) rz) 9i
Ōr:
lapa(x) (2) za exp(-Ixz/a)),
or equivalently:
which, for 0, corresponds to the density of the Laplace distribution.
db x²
dr
We put
r() p: (apa(x- -z) E 1],
C.2. Derivatives of Top
We put
8; (apa(((r k) r:) 2a exp(-1
pe(r; w; = Tapa (b-rz) where = Lap-Sum (r, k; a:).
1 min(p: 1-).)- p.).
Observe that (p;) is exactly the solution given by LapSum to soft top-k problems.
We will need the following notation:
Sa(w)= = Σ St.
q 5 (sa,.... .000...,880.......... .n-1))
Derivatives of pi(ri....., k) with respect to k We
softmax
---00
have:
Öp: δ
Øb
After establishing the necessary notation we proceed to computation of the derivatives.
Lapa(b(r.)) k) re) lopa rz) Ok Ōk ak
Substituting into (10), we get:
C.1. Derivative of inverse of Lap-Sum
Öp. lapa (b(r. k)) r;)
Derivative of Lap-Sum" -1 with respect to Differen- tiating (9) with respect to k, we get
dw
E, lapal (II, - b(xx k))
0b
Thus:
Σ
lapa (b(r, w. a)
- -r)) Dw
1,
dp dk q.
which leads
db
ak E, (apr k) k) r,
S'
(10)
Derivative of p(,, k)) with respect to Lapa (b(r, k)) -r))= Lap
We have:
Öp: δ
θ
b-
Derivative of Lap-Sum with respect to a Differen- tiating (9) with respect to a, we get:
da da
da
a
lopa kb) (T))
abb
b
ri
ab Bn
(b - r:) 0.
da
a
Σ Cap. (b r;)
Substituting:
Öp: (bpa - -r)): (b. - (g,r)
b
r
As result,
da
a
+
a
0b da
E, lapa
b-re
(b rz)
8; (ri - (g, r))
Σ, lapac
b-ri
a
Thus:
(b (g,r)).
Op -s (g.r)s))
(1I)
da
12

---

LapSum: One Method to Differentiate Them All
Derivative D of p(: with respect For D [dayl.
Thus:
have:
du 1 Or- h(p)).
da a (h(p)
dy 0p, = (b(r, -4))
(
@b
0is)
Òr:
θr:
Derivative of with respect to r We have
Thus (in column vector notation):
Du ddiag (t) Dp =daa
( (sq" diag(s))
0b
D = [Lapa (b rz)]
diag(lapa (b -r:))
dr;
(h(p)q (iag(((()))
=sq" - diag(s).
- -Derivvvvee with respect to r in the direction
Derivative of p(-, k) in the direction Since we want to compute without declaration of all matrix, we get the derivative in the direction o:
du dr (e) ((g. u) h(p) - v o h(p)),
where denotes componentwise multiplication.
D e qs [s)] v (a, s-
where @ denotes componentwise multiplication.
Dual case: computation of o" Du We have
T Du _ ((v. (()))(p)) - h())))
Computing TT D We have 8f o DD= = of g diag(s)] = (s. of
C.4. Derivatives of (kz) - (Tap-Sum (r:k:))==0..--
C.3. Computing derivatives for the function u = logp
We shall now consider the case when the input is k = (A:) Rt This happens in particular in LapSum for soft sorting or the computation of soft permutation matrix.
In some cases, especially for CE loss, we will rather need log p instead of p.
Value of l
We have:
We put
log pi = b-r: T3
b, = bb,r, b,(r,k;; k; = Lap-Summ (r,ks)
and
where:
B B(r k; a)) (bi) RR Our aim is to compute the derivatives of the function B with respect to w, r and a. We apply here the formulas from Appendix C.I.
log 2 + log(2 - exp(-lx()) for 0, for x < 0.
g(x)
log 2 + x
To calculate derivatives, we need the auxiliary function:
We first introduce matrix Q which is defined as
for x I
h(x) - for 1
Q =
Derivative with respect to A We have
where Qm _ is the (column) vector defined by
du: 1
0p:
Ōk
pi
Pi
Om = softmax(
bm-ru
dm TN-1
R".
Thus
Du:
Derivative over a
We have
= g/p = (p)
0k
Øb
(b Q.r).
da
Derivative of with respect to
We have:
Derivative over w
We have
Ou
1
Op
2
DB
da
p
da
diag 1m
0k
Substituting:
where
Du
0 (s
1
(g.r) s).
Sm 2a
Σ
exp(= -
bm Om-
da
p
a
13

---

LapSum: One Method to Differentiate Them All
Derivative over
We have db Q.
0.86
dr
Fast computation Our aim is to show how one can efficiently compute the left and right multiplication of the above derivatives by vectors. We present here the general idea for fast computation of all (Si). the other calculations can be done by applying a similar approach. For clarity of presentation, we restrict to the case =
Ps
15000.5
Trainable
(0000
(D000
11
<5000 -1000
-100
-10
45000 1100
-100
-10
Figure 8. ImageNet-IK Top-1 and Top-5 accuracies of LapSum across varying values of a and P.. Larger a's produce "harder", more discrete selections while smaller lead smoother outputs. This trade-off influences how strictly the model enforces a top-k criterion
So assume that we want to efficiently compute the values
Dm Σ exp(- lbr rzl)
1=0
for all m, that is, in a smaller complexity than OLL n)). As before, we assume that the sequences and are in an increasing order. Observe that
ing rates. We select a from (-1.5, -0.5, -0.2, -0.1]
and Leaning Rate (LR) from {10 10 10-4.5, 10 10-4.25 10-4, 10 10- 3.75 10 3.5 10 3.25 10 10-3.0, using early stop- ping approach too. See Fig. 8 for influence of a param- eter on model performance. Baselines As baselines, we reuse scores reported (Petersen et al., 2022b). Imple- mentation We use code from https: /ttp:///githbb com/ Felix-Petersen
Dm = Am + Bm:
where
Am
Σ
exp(r: - bm), Bm
exp(bm rs).
ffookk kindly made available by Petersen al. (2022b). Hyperparameter details are avail- able in Tab. 5.
Br bb..
Let 7m = min(i E {O...., n 1} rs > bm (and n there is no satisfying this condition). Then since the sequence r increasing we obtain that
Table 5. The hyperparameters for training CIFAR-IO0 from scratch
-1
Am
exp(r: - b,, Bn = Σ exp(bm - rz).
and fine-tune of ImageNet-I IK and ImagoNet2IK models.
CIFAR-100
ImageNet-IK
ImageNet-21
1=U
7m
Batch size
100
500
500
Clearly, since sequences and are increasing we obtain that
#Epochs
200
100
40
best LR
10 10-3.25
10 10-4.25
10 10-4.75
best a
-1.5
7 S Rm++1
Model
ResNet18
ResNeXt-101
ResNeXt-101
Consequently
Pmmt1
Am+1 exp(bm bm+1): Am +
Σ exp(r: bm+1)
k-NN for Image Classification We adopt an identical experimental setup (Xie al., 2020), which follows the approach of Grover et al. (2019). A grid search was con- ducted to fine-tune both the parameter of LapSum and the learning rates. We set a as network trainable parameter. We select a at to from {-10, -5, -1.5,, -1, -0.5, -0.2, -0.13 and Leaning Rate (LR) from (10-4.75 10 10-4.5 10 10-4.25 10-4, 10 10-3.75, 10-3.5 3.5 10-3.25 10-3.u 10-2.75). also using early stopping. For details see Tab. 6. Baselines The baseline results are taken directly from Xie et al. (2020), which in turn references Grover et al. (2019) and He et al. (2016). Implementation We use the code kindly made available by Xie et al. (2020), which itself builds on Cuturi et al. (2019) and Grover et al. (2019).
and
Bm = exp((b bm+1) Bm+1+ exp(bm r:).
1m
Therefore, we can first compute Ag and B,-1. and com- pute the rest by the above iterative formulas. Finally, the complexity of the computations O(L + n) instead of On..n).
D. Experiments
Training from scratch on CIFAR100 and fine-tuning on ImageNet We adopt the identical experimental setup as (Petersen et al., 2022b) using the Adam optimizer (Kingma & Ba, 2015) for all models. A grid search was conducted fine-tune both the a parameter of LapSum and the learn-
Trainable Parameter a in Soft-Permutation Exper- iment our method, as described in the experiment in Sec. 5.2, we introduce trainable parameter a that can
14

---

LapSum: One Method to Differentiate Them All
et al., 2023). Figs. 10 and 11 present the time complexity and memory usage of all the soft top-k methods considered when executed on CPU. Similarly, Figs. 12 and 13 show the same metrics, but computed on a GPU. These figures illustrate the relationship between runtime, memory con- sumption, and data dimensionality n, with A = n1/2. Across all scenarios, our approach (represented by the solid blue line) consistently outperforms or matches the best compet- ing methods, particularly for higher data dimensions. Some competing algorithms fail to complete tasks due to excessive memory requirements, further highlighting the efficiency of our method. In addition, we include critical difference (CD) diagrams to statistically validate performance com- parisons (Demšar, 2006). The CD diagrams confirm that our method ranks within the top-performing group of al- gorithms, demonstrating its superiority in both time and memory efficiency across CPU and GPU implementations. These results reinforce the robustness and scalability of our approach in practical applications.
Table 6. N-NN experiments' hyperparameters.
Dataset
MNIST
CIFAR-II
10
k
9
9
Batch size of query samples
100
100
Batch size of template samples
100
100
Optimizer
SGD
SGD
Number of epochs
200
200
Best LR
10 2.75
10 1023.25
Best a
-10
Momentum
0.9
0.9
Weight decay
5
10-4
5 10-4
Model
2-layer CNN
ResNet18
Train LoGs
255
4.5
125
The performance of soft permutation methods is visualized in Fig. 14 where the data dimension n on the horizontal axis is compared the memory usage and the computation time on the vertical axis. Computations were performed a CPU due to the high memory demands of some of the considered methods. Results are shown for the forward process (left column) and the forward-backwall process (right column). Our implementation is in PyTorch, while the other methods are implemented in TensorFlow. Our approach demonstrates superior scalability and efficiency, particularly for large achieving faster computation times and lower memory usage compared to the other methods.
Figure 9. Results from one of the experiments in Sec. 5.2, showing the cost function (blue line) and the learning rate alpha (orange line) over training iterations. The cost function decreases as the model learns, indicating convergence. Parameter a starts at 0.4, initially decreases to allow for finer updates, and then increases to a value above to accelerate learning in later stages.
be optimized on the basis of gradient during the training process. This parameter plays a crucial role in controlling the dynamics of the soft- permutermttatinn mechanism, allowing the model to adaptively balance between exploration and exploitation during learning. LapSum stays fully differen- tiable for all a f O.
Fig. 9 illustrates the evolution of a alongside the cost func- tion over the course of training iterations. The blue line represents the cost function, which decreases smoothly and consistently, indicating stable convergence of the model. The orange line tracks the value of a, which starts an ini- tial value of 0.4. Initially, a decreases to facilitate finer and more precise updates to the model parameters. As training progresses, a increases to value greater than 1, allowing faster learning and greater updates at later stages of training. This adaptive behavior of a demonstrates its effectiveness in guiding the optimization process, ensuring both stability and efficiency learning.
Error, Runtime and Memory Analysis We provide a de- tailed runtime and memory analysis of our method com- pared to other approaches. We use float64 precision when- ever possible and float32 otherwise. Methods that sup- port float64 precision are: LapSum (ours), Optimal Trans- port (Xie et al., 2020), SoftSort (Prillo & Eisenschlos, 2020), Fast, Differentiable and Sparse TDykk(Dy)) (Sander
15

---

LapSum: One Method to Differentiate Them All
(Blonid)
Topal jours)
Siender 2023 (Dylutta) Sander et al....22 2023 (PAX)
[Optinal Transport)
Grover etal. 2019 NourrBoort
Patersen ai, 2022 (8p flar Selectior)
Forward
Forward Backward
10
Puntime (s)
10a
109
10
10:
10a
Nemory (GB)
10a
10
Dimensions
Dimensions
Critical difference diagram
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Sander et al., 2023 (Dykstral [0.25]
[1.00] Lap-Top-k (ours)
Grover all, 2019 (NeuralSorti 29]
[0.69] Xie et al., 2020 (Optimal Transport)
Batcher, (Bitonic) [0.34]
al.,
[0.48] Petersen et 2022 (Splitter Selection)
Figure 10. Relationship between the dimension (rt), shown the horizontal axis, and the maximum memory usage and computation time on vertical axis, for several functions with a fixed h 5. All calculations displayed in this graph were performed on a CPU, The evaluation examined memory consumption and execution time during the forward pass (left column) and the combined forward and backward passes (right column).
Betcher: 1998 (Bhonic)
Lap Top (ours)
Sander et al.. 2023 (Dylsttra
Xe et 2020 JOstinal Transport
Grover etai. 2019 (louralSort)
Petersen et 2022 15p itter Selectio)
Sander at. 2023 (PA))
Forward Backward
10a
Buntime 18
10a
109
10
10a
Memory (G8)
201
10a
10a
104 Dimensions
103
10a
107
102
10a
104
10
10
107
Dimensions
Critical aifference diagram
0.2
0,4
0.6
0.8
1.0
Peterson et oal,, 2022 (Splitter Selection) [o.1
[1.00] Lap-Top-k (ours) Xie et (Ostimal Transport)
Batcher, (Bitonic) [0.30]
Sander 2023 (Dylestra) [0.40]
Sander 2023 (PAV) [0.44] Grover et. 2019 (NeuralSort)
Figure 11. Relationship between the data dimension (n), represented on the horizontal axis, and the maximum memory usage and computation time, represented
vertical axis. The parameter k was dependent on n, calculated using the formula n/2. The computations depicted in this figure were performed on CPU, The relationships between time and memory usage were analyzed during the forward process (charts left column) and forward and backward processes (charts the right column).
16

---

LapSum: One Method to Differentiate Them All
(Brionic) Grover et al, 2019 (NautBBort)
Top- (ouns)
(Dykstra)
Transport)
Pelersen at di, 2022 (Splitter Sweectio)
Sander at al. 2023 (PAV)
101
Forward
Forward
10
Bunlime (S)
10-1
10a2
10-3
Veeoryy (68)
104
10
10
10a
10a Dimensions
10a
10"
10a
10a
10a Dimensions
10"
20
Critical difference diagram
0.5
0.6
0.7
1,0
Batcher, 1968 (3itonic) [0.29]
[0.99] pop-lop-kk
Sander et al., 2023 (Dykstra) [0.30]
[0.67] Xie et al., 2020 (Optimal Transport)
Grover et al., 2019 Sorth [0.41]
10. 50. Sander et al., 2023 (PAV)
[0. [0.42) Petersen al., 2022 (Splitter Selection)
Figure Relationship between dimension n (horizontal axis) and the maximum memory usage computation time, represented the vertical axis, for several functions with fixed & 5. All caleulations displayed in this graph were performed GPU. The evaluation examined memory consumption execution time during the forward pass (left column) and the combined forward backward passes (right column).
Batcher, (Bitonic)
Lep-Top-k (ouns)
Sander al. (Dykstra)
et 2020 (Oplima Transport)
Grover 2019 Sort)
Petersen et 2022 (Splitter Selection
Sonder al. 2023 (PAV) Forward & Backward
103
Forward
10F
Burtime
10
10-2
10-3
Menrryy (69)
303
10a
10a
10 Dimensions
10a
10a
10'
10
10f Dimensions
10a
10*
Critical difference diagram
Petersen (Splitter Selection! [0.17]
[0.96] Lap-Top-k (ours)
Batcher, 1968 (Bitonic) [0.31]
[0.67] Xie et al. 2020 (Optimal Transport) [o.Se] Sander et al., 2023 (PAW)
Sander et al., 2023 (Dylstraa [0.35]
(NeuralSort)
Figure 13. The figure illustrates the correlation between the dimensionality horizontal axis and the peak memory usage well computation time, on vertical axis, for various functions with k = n/2. All computations depicted in this graph were executed on GPU. The analysis focused on memory utilization and runtime during both the forward pass (left column) and the combined forward and backward passes (right column).
17

---

LapSum: One Method to Differentiate Them All
Deteministic Neuralsort
Gumbel Sinkhom
Lap-Parm (ours)
Sinkhom
Stochastic
Vanila
Forward
Forward & Backward
Runtme
10
Memory (MB)
101
10'
10
10
10
10
10"
10
Dimensions
Dimensions
Figure The performance of soft permutations methods, plotting data dimension n on horizontal axis versus memory usage and computation time the vertical axis. Computations were performed a CPU due to the high memory demands of some of the considered methods. Results are shown for forward process (left column) and forward-backward process (right column). The implementation method is in PyTorch, while the others implemented in TensorFlow. Our approach demonstrates superior scalability and efficiency, particularly for large n, achieving faster computation times and lower memory usage compared to the other methods.
18


Reviews:
[{"review_id": "WJDoYTzIgJ", "reviewer": "Reviewer_UBWD", "summary": "This paper proposes a new method for computing differentiable approximations of ranking, sorting and top-k operators. This method is based on considering sums of the CDF of the Laplace distribution, which defines the approximations for well chosen arguments, with a regularization term $\\alpha$. The choice of the Laplace distribution is motivated by the fact that the proposed operators can be computed and differentiated in closed form efficiently in this case, as formally detailed in the paper.\nThe method is illustrated for top-k selection in multilabel classification on CIFAR and Imagenet, as well as k-nn for Image classification on MNIST and CIFAR and soft-permutation on MNIST.  \nExperimental results also validate the computational and memory efficiency of the proposed approach for the top-k operator, either surpassing or competing with previous approximations on different hardware.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very careful reading and insightful review of our paper. We address your questions as follows:\n\n1. Why haven't we considered sorting and ranking applications?\n   \n   Our research focused on designing an efficient model with a closed form for soft ordering tasks, and we defined models for both ranking and sorting. For applications, we deliberately aligned with Petersen's established framework to facilitate meaningful comparisons. Our experimental scope was partially constrained by implementations that allow cross-entropy loss value comparisons. Nevertheless, we conducted experiments for both sorting and ranking using LapSum, achieving results comparable to existing solutions. These will be included in the final version. [Link to figures with comparison of ranking and sorting solutions.](https://anonymous.4open.science/r/icml25-7AB6/README.md)\n\nResults for sorting methods on forward (CPU, 10* - space dimension):\n|Metric|Method|10⁷|10⁶|10⁵|10⁴|10³|\n|:-|:-|-:|-:|-:|-:|-:|\n|Mean time|Lap-Sort|59.944|6.163|0.596|0.059|0.009|\n||Blondel et al.|98.884|6.077|0.443|0.044|0.007|\n|Max memory(MB)|Lap-Sort|43.36|4.74|0.87|0.49|0.45|\n||Blondel et al.|29.09|3.44|0.84|0.57|0.56|\n\nResults for ranking methods on forward (CPU, 10* - space dimension):\n|Metric|Method|10⁷|10⁶|10⁵|10⁴|10³|\n|:-|:-|-:|-:|-:|-:|-:|\n|Mean time|Lap-Rank|32.379|2.81|0.245|0.021|0.003|\n||Blondel et al.|110.712|6.034|0.437|0.04|0.008|\n|Max memory|Lap-Rank|33.83|3.85|0.85|0.55|0.52|\n||Blondel et al.|19.53|2.45|0.75|0.57|0.55|\n\n2. Justification for using our model over Xie's given comparable computation time and memory\n   \n   While both models demonstrate similar computational efficiency as shown in our statistical tests (Figures 5, 7), LapSum outperforms Xie's model in all but one test. Both methods offer high accuracy (important in application, as Xie notes) and handle all derivatives effectively. However, the key advantage of our approach is its closed-form solution, whereas Xie's method relies on an iterative approach for both the model and its derivatives. This closed-form formulation provides theoretical elegance and potentially better stability in complex applications.\n\n3. Missing reference to Berthet's paper\n   \n   We acknowledge the omission of Berthet et al. 2020 \"Learning with differentiable...\" paper. While we referenced a Blondel et al. 2020 \"Fast differentiable...\" paper which addresses related solutions, we will include Berthet's work in our final version, as it aligns very well with our approach and provides excellent context on related research.\n\n4. Theoretical claims\n   \n   Thank you for your detailed analysis. We confirm that:\n   - The definition in line 154 should indeed be $(F-Rank_\\alpha(r))_k$ and will be corrected. In later lines, where some indices may be obvious, we shall note it clearly.\n   - For $F-Sort_\\alpha$ (line 125), we will add a footnote clarifying that $r$ in the definition is the default parameter.\n   - In Theorem 3.2 proof the ${1}\\over{2}$ is the value of $F_\\alpha$ function at $0$, see e.g. Fig.2. The mismatch between the formulation and proof of the theorem is a typo to be corrected.\n   - The proof for $F-Sort_\\alpha$ is very similar, and we can add it in the final version.\n\n5. Experimental issues\n   \n   We appreciate your positive assessment of our experimental flow. Regarding standard deviations in experiment tables: we relied on published results from other researchers where original code wasn't always available. Reimplementing these approaches would introduce potential inconsistencies and errors. Consequently, we cannot provide deviation values at this stage but acknowledge this as an area for future work.\n\n6. Potential overstatement in abstract\n   \n   Our intention was to emphasize that our tool is theoretically sound, offers a closed-form solution, and is computationally competitive for high-dimensional spaces. The wording was not meant to imply superiority but rather computational competitiveness. We will revise this to better reflect our position.\n\n7. Typographical errors\n   \n   We will correct all identified typos (as addressed above) to improve clarity. Regarding \"doubly stochastic matrix\" we were referring to permutation matrices $P_{k,c}$ that are both row- and column-stochastic, as described in Petersen 2022 \"Differentiable top-k...\" The $n$ and $k$ in the introduction denote the space dimension and the number of top values to be selected — this shall be clarified. Thank you for careful reading.", "claims_and_evidence": "- the efficient calculation of the Lap-Sum, its inverse and derivatives are supported by convincing mathematical evidence. I nevertheless think it would have been clearer to formalize the results of paragraph \"Calculation of inverse function\" (l.269) and section 4.2 (derivatives) with a proposition, as is done for section 4.1. \n\n- the fact that $F-Rank_\\alpha$ and $F-Top_\\alpha$ approximate the ranking and top-k operator is supported by convincing mathematical evidence. I would have expected the same for $F-Sort_\\alpha$, for which, unless I am mistaken, a proof is missing.", "methods_and_evaluation_criteria": "The paper considers evaluations and methods that were used in prior works, such as Petersen et al. (2022b), Berrada et al. (2018), and Grover et al. (2019). The evaluations mostly concern the top-k operator, with also one experiment on soft-permutations.\n\nTo me, the evaluation makes sense for the problem and application at hand, but it would have strengthened the paper to add applications on sorting and ranking, such as the ones in Blondel et al., 2020, or in Berthet et al., 2020 (Learning with Differentiable Perturbed Optimizers).", "theoretical_claims": "I checked the proofs in the main text, which seem okay to me despite some typos.\n\n- The fact that F-Rank_alpha is applied at $r_k$ in l.154 versus applied on $r$ in theorem 3.2 is confusing. I understand that l.154 should be $(F-Rank_\\alpha(r))_k$ instead?\n- For the proof of theorem 3.2, can the authors clarify why there is a 1/2 factor which we don't have in the theorem?\n- The definition of F-sort_alpha involves the inverse of F-sum_alpha, but this one is only evaluated with one argument, whereas it expects two arguments (see l.125, for instance).\n- Typo in the definition of F-Top_alpha.", "experimental_designs_or_analyses": "- Yes, I checked the soundness/validity of the experimental designs, which are mostly adapted from previous works. I did not notice any issue despite the aforementioned one, which consists of missing experiments for the sorting and ranking operators.\n\n- I appreciated the empirical validation of the efficiency of the proposed method for top-k selection.\n\n- Displaying the std for the results in the tables would have been helpful to validate the statistical significance of the results.", "relation_to_broader_scientific_literature": "The key contributions of the paper are quite well related to the broader scientific literature. The paper clearly cites existing papers proposing competing methods, and compares itself to these methods in terms of accuracy (top-k classification, soft-permutation, k-nn in tab 1-4) as well as efficiency (space and time complexity).\n\nHowever, I still think that a comparison is missing for sorting and ranking, since the experimental part of the paper solely focuses on top-k and soft-permutations.", "essential_references_not_discussed": "Most papers I know about in the differentiable programming area to propose relaxations of sorting, ranking, or top-k operators are discussed, except Berthet et al., 2020: Learning with Differentiable Perturbed Optimizers, which is clearly aligned with the topic considered, by proposing soft ranking operators for label ranking applications.", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper proposes a method that is faster than existing ones for computing and differentiating differentiable approximations of the top-k operator.\n\n- The method is easy to understand and to implement.\n\nI tend to lean towards acceptance of the paper, but there are a few weaknesses that bother me:\n\n- The paper introduces differentiable approximations for sorting and ranking, but these are not considered in the experimental part of the paper.\n\n- The sentence \"Through extensive experiments, we demonstrate that our method outperforms state-of-the-art techniques for high-dimensional vectors and large k values\" feels like an overstatement to me. It is true that the proposed method outperforms existing ones in terms of speed and memory (even though I did not see any experimental analysis for sorting and ranking), but it does not demonstrate superiority in terms of accuracy.\n\n- There are too many typos.\n\n- The method is really comparable to Xie et al. (2020) in terms of efficiency: can the authors comment on the advantage of their method compared to this one? Why should we use one instead of the other?\n\n- The proposed top-k operator is not sparse (in the sense that as soon as $\\alpha \\neq 0$, all the coefficients will be non zero). This should be mentioned because this prevents the use of the operator for pruning weights in neural networks or for mixture of experts.", "other_comments_or_suggestions": "I strongly suggest the authors carefully proofread the paper to eliminate the typos. Here is a non-exhaustive list:\n\n- l. 26: optimal transport-based?\n- l. 29\n- l. 33: what are n and k?\n- \"Techniques employed to solve these problems include relaxations and estimators, ranking regularizers, even learning-based ranking solutions\": add references.\n- l. 69: \"value of k\" + parentheses for the ref.\n- l. 117: I find it misleading that F_alpha and f_alpha correspond to two different formulas, but this is a detail.\n- l. 154: inconsistency between the definition of F_rank here and in thm. 3.2 (in terms of argument, scalar vs. vector).\n- l. 170\n- l. 215: doubly stochastic?\n- l. 270: the function?\n- l. 305: Appendix x2\n- l. 410", "questions_for_authors": "- Why haven't you considered applications to sorting and ranking ? \n\n- Lap Sum is really comparable to Xie et al (2020) in terms of computational and memory efficiency: can the authors comment on the advantage of their method compared to this one ? Why should we use one instead of the other?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QEKdSYlrQM", "reviewer": "Reviewer_wMdT", "summary": "Authors propose “LapSum” - that yields differentiable versions of ranking, sorting, top-k selection, and permutations, all in closed form, with low time complexity: O(nlogn) (same as any sorting algorithm), and a linear memory.\n\nAuthors define this F-sum function and then define the ranking task in terms of F-sum function. \n\nThe main contributions is: 1) Defining all “soft” ordering tasks can be built by plugging the relevant r and appropriate $\\alpha$ and then inverting or evaluating F-Sum(\\alpha). A naive approach would need iterative solutions and result in O(n^2) complexity. 2) Authors choose \nF as the CDF of the Laplace distribution, the computations become both closed-form and O(nlogn) complexity.\n\n## update after rebuttal\n\nI had one clarification question around experiments with learning-to-rank datasets, and authors clarified that it is not the norm in related works to experiment with learning-to-rank datasets, and authors experimental setup is indeed valid. My original assessment (4) has not changed.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our paper.\n\n1. Related references\n   \n   We appreciate your suggestions regarding additional references. Our literature review focused primarily on differentiable soft ordering, ranking, sorting, and top-k methods as addressed in works by Cuturi, Lapin, Berrada, Petersen, Blondel, and others (all included in bibliography). While our primary aim was to propose a new theoretically well-founded and computationally efficient tool to compare with these approaches, we acknowledge the importance of gradient boosting stochastic smoothing methods and Plackett-Luce based models. We will include these references in our revised manuscript.\n\n2. Experiments\n   \n   For direct comparisons, we utilized applications addressed in existing literature, such as top-k classification and permutation matrix classification, particularly in high-dimensional spaces. While the additional datasets you suggest are very valuable, incorporating them would extend beyond our current scope. We plan to evaluate our framework on a wider range of applications in future work.\n   \n   Regarding experimental setup, we followed protocols established in the aforementioned literature to ensure direct compatibility, as our main goal was to develop a well-grounded and computationally effective tool. The direct comparisons with boosting approaches are in plans for our research.\n   \n   We have not included soft ranking due to limited availability of solutions with probability values. However, we have defined the LapSum approach for both ranking and sorting tasks and will include these results in the final version. [Link to figures with comparison of ranking and sorting solutions.](https://anonymous.4open.science/r/icml25-7AB6/README.md)\n\nResults for sorting methods on forward (CPU, 10* - space dimension):\n|Metric|Method|10⁷|10⁶|10⁵|10⁴|10³|\n|:-|:-|-:|-:|-:|-:|-:|\n|Mean time|Lap-Sort|59.944|6.163|0.596|0.059|0.009|\n||Blondel et al.|98.884|6.077|0.443|0.044|0.007|\n|Max memory(MB)|Lap-Sort|43.36|4.74|0.87|0.49|0.45|\n||Blondel et al.|29.09|3.44|0.84|0.57|0.56|\n\nResults for ranking methods on forward (CPU, 10* - space dimension):\n|Metric|Method|10⁷|10⁶|10⁵|10⁴|10³|\n|:-|:-|-:|-:|-:|-:|-:|\n|Mean time|Lap-Rank|32.379|2.81|0.245|0.021|0.003|\n||Blondel et al.|110.712|6.034|0.437|0.04|0.008|\n|Max memory|Lap-Rank|33.83|3.85|0.85|0.55|0.52|\n||Blondel et al.|19.53|2.45|0.75|0.57|0.55|\n\n3. Theoretical claims\n   \n   Thank you for recommending a more formal definition connecting ranking to the CDF. We will incorporate this description to improve clarity, following your recommended approach. A key advantage of LapSum is its theoretically elegant closed-form solution, naturally not forgetting its computational efficiency. This non-iterative approach provides enhanced stability compared to existing methods that rely on iterative processes.\n\n4. Other concerns and concluding remarks \n\n   We believe we have addressed your primary concerns and will implement the suggested improvements in our final manuscript. In the revised version, we will add the missing references to better describe the related research field, include a formal description of ranking and CDF, and more clearly articulate the impact of our proposal on the field.", "claims_and_evidence": "The claims made hold theoretically, and empirically, though I have some reservations (more of that in questions to the authors section).", "methods_and_evaluation_criteria": "Authors use benchmark datasets used in previous papers from the \"differentiable sorting\" literature. I have some additional comments (more of that in questions to the authors section).", "theoretical_claims": "The theoretical claims seem to be correct, though I didn't get a chance to go through all of the steps in all proofs.", "experimental_designs_or_analyses": "I am not fully convinced with the experimental setup. I am open to discussion with the authors on this.", "relation_to_broader_scientific_literature": "The paper proposes a model for learning to rank task, which is critical to many real world applications.", "essential_references_not_discussed": "Authors didn't discuss the connection (or a lack of) with the following differentiable ranking works:\n\n1. Ustimenko, Aleksei, and Liudmila Prokhorenkova. \"Stochasticrank: Global optimization of scale-free discrete functions.\" International Conference on Machine Learning. PMLR, 2020.\n\n2. Oosterhuis, Harrie. \"Learning-to-rank at the speed of sampling: Plackett-luce gradient estimation with minimal computational complexity.\" Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2022.\n\n3. Sakhi, Otmane, David Rohde, and Nicolas Chopin. \"Fast slate policy optimization: Going beyond Plackett-Luce.\" arXiv preprint arXiv:2308.01566 (2023).", "other_strengths_and_weaknesses": "The writing of the paper could be improved, for example the connection of the CDF with the ranking task is not immediately clear. It would be helpful if authors first formally write down the ranking task (for ex: rank as sum of indicator function etc. to connect with a CDF). \n\nAlso, the method is designed for ranking tasks, but popular learning to rank datasets/tasks are missing, for ex: MSLR, Yahoo etc LTR datasets [1]. \n\n\n1. Ustimenko, Aleksei, and Liudmila Prokhorenkova. \"Stochasticrank: Global optimization of scale-free discrete functions.\" International Conference on Machine Learning. PMLR, 2020.", "other_comments_or_suggestions": "As I noted in the previous section, if the authors can first formally introduce the ranking task (mathematically) and it's connection with CDFs and the math following, it would be more helpful for the readers.", "questions_for_authors": "Please see my comments previously about the lack of connections to some previous works and lack of learning to rank datasets/task.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M05vBOLuiT", "reviewer": "Reviewer_m9fB", "summary": "LapSum introduces a unified method for creating differentiable versions of ordering operations—such as ranking, sorting, and top‑k selection—by leveraging a closed-form inversion of the Lap-Sum function (the sum of Laplace CDFs). This approach allows efficient gradient computation in $O(n \\log n)$ time while using only $O(n)$ memory, making it well-suited for high-dimensional data. The theoretical framework shows that these soft approximations converge to their hard, discrete counterparts. Extensive experiments on datasets like CIFAR‑100 and ImageNet demonstrate competitive or superior performance compared to existing methods, and the availability of both CPU and CUDA implementations underscores its practical applicability in large-scale neural network training and optimization tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and constructive suggestions for improving our paper.\n\n1. Applications of our method\n   \n   Our paper introduces several applications including top-k learning, soft ranking, sorting, and permutation learning. To address your request for concrete examples:\n   \n   - Vector Quantized-VAE models can directly leverage our differentiable sorting approach in their codebook optimization process, improving representation learning efficiency.\n   \n   - Large Language Models benefit from our ranking method when analyzing token distributions and building optimized dictionaries, enabling more effective model analysis and interpretation. Finding the dictionary of a trained Transformer dictionary provides a method for its deeper analysis.\n   \n   We have included pseudocode for the LapSum model in Appendix A, designed for straightforward implementation. Additionally, the attached code contains complete implementations in both PyTorch and CUDA, with performance competitive with existing methods.\n\n2. Experiments\n   \n   While our paper focused primarily on classification applications, we will expand the experimental section to include soft ranking and sorting evaluations. These additions will demonstrate that LapSum provides a unified approach applicable across all differentiable soft ordering problems. The results will show comparable or superior performance to specialized methods while maintaining our closed-form advantages. [Link to figures with comparison of ranking and sorting solutions.](https://anonymous.4open.science/r/icml25-7AB6/README.md)\n\nResults for sorting methods on forward (CPU, 10* - space dimension):\n|Metric|Method|10⁷|10⁶|10⁵|10⁴|10³|\n|:-|:-|-:|-:|-:|-:|-:|\n|Mean time|Lap-Sort|59.944|6.163|0.596|0.059|0.009|\n||Blondel et al.|98.884|6.077|0.443|0.044|0.007|\n|Max memory(MB)|Lap-Sort|43.36|4.74|0.87|0.49|0.45|\n||Blondel et al.|29.09|3.44|0.84|0.57|0.56|\n\nResults for ranking methods on forward (CPU, 10* - space dimension):\n|Metric|Method|10⁷|10⁶|10⁵|10⁴|10³|\n|:-|:-|-:|-:|-:|-:|-:|\n|Mean time|Lap-Rank|32.379|2.81|0.245|0.021|0.003|\n||Blondel et al.|110.712|6.034|0.437|0.04|0.008|\n|Max memory|Lap-Rank|33.83|3.85|0.85|0.55|0.52|\n||Blondel et al.|19.53|2.45|0.75|0.57|0.55|\n\nWe appreciate your thoughtful feedback and believe these clarifications and additions will strengthen the paper considerably.", "claims_and_evidence": "I think the evidence is generally clear and convincing.", "methods_and_evaluation_criteria": "The methods are well-justified for the problem at hand.", "theoretical_claims": "I have not checked the proof, but theorem statements are reasonable for me.", "experimental_designs_or_analyses": "The experimental design is generally sound.", "relation_to_broader_scientific_literature": "The paper situates its contributions within a growing body of work on differentiable ordering operations. Previous approaches often faced challenges in computational efficiency or relied on iterative procedures, LapSum introduces a closed-form inversion using the Lap-Sum function, leading to a unified framework that efficiently computes gradients in O(n log n) time and requires only O(n) memory.", "essential_references_not_discussed": "I am not familiar with literature at all.", "other_strengths_and_weaknesses": "- Strengths: From my perspective, I think this paper is well-written, and novel in the sense that this it proposes unified framework for differentiable ordering that creatively combines ideas from previous works on smooth approximations with a closed-form solution using the Lap-Sum function.\n\n- Weakness: since I am not familiar with literate, experinments only focus on the calssification tasks, which might hurt the broad implicaition of the current method. Another application can be done to demonstrate the generality of the approach.", "other_comments_or_suggestions": "Overall, I find the paper both rigorous and engaging. However, for readers like me who may not be deeply familiar with the literature, it would be beneficial to include concrete examples that explain in greater detail the importance and applications of ranking, sorting, and top‑k selection. Additionally, incorporating a concise pseudocode or algorithmic summary that outlines the key steps of LapSum in the main text would help clarify the intuition behind the algorithm and its general use.", "questions_for_authors": "See the comment above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents LapSum, a method for differentiable ranking, sorting, and top‑k selection using a closed-form inversion of a Laplace-based sum. It offers memory-efficient gradient computation and applies to high-dimensional settings. The approach is theoretically sound, and scales well on both CPU and GPU. While experiments focus mainly on top‑k tasks, the authors provide additional results and definitions for sorting and ranking.

I recommend acceptance. The method is original. Its closed-form nature sets it apart from prior iterative approaches. Despite minor presentation issues, the authors addressed reviewer concerns and clarified their contributions. This work is a valuable addition to differentiable optimization research.
Decision: Accept (poster)