Research map / Learning theory and algorithms / Prediction and decision losses
LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LapSum, a closed-form differentiable soft ranking, sorting, top-k, and permutation method built on the inverse of a sum of Laplace CDFs, giving O(n log n) time and O(n) memory with forward and backward passes.
Problem
Sorting, ranking, top-k selection and permutations are piecewise constant and non-differentiable; existing differentiable relaxations are often computationally expensive (time/memory), lack closed forms, or do not yield probabilities, limiting use on large n and k.
Approach
Use the sum of Laplace CDFs as a soft counting function; its inverse has a closed-form expression computable in O(n log n) (sorted input, prefix-style recurrences), so soft top-k probabilities, soft ranks, soft sorts and doubly stochastic permutations follow with analytic derivatives computable in O(n log n) via left/right vector products.
Key results
- On CIFAR-100 with ResNet18 and top-5 training, Lap-Top-k reaches 58.07 ACC@1 vs 55.62 for SinkhornSort (uniform-P setting: 64.53 ACC@1).
- On ImageNet-21K-P fine-tuning with P=[0,0,0,0,1], Lap-Top-k gets 37.93 ACC@1 and 70.67 ACC@5, the best in that table; ImageNet-1K results are on par with others (~85.5 ACC@1).
- On Large-MNIST with n=3, Lap achieves 94.2% permutation accuracy vs 93.0% for deterministic NeuralSort; it trails NeuralSort at n=9 and n=15.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Lap-Top-k instead of SinkhornSort | ResNet18 · CIFAR-100, P_j=[0.,0.,0.,0.,1.] | ACC@1: 55.62 -> 58.07 | Helped |
| Use Lap-Top-k instead of DiffSortNets | ResNet18 · CIFAR-100, P_j=[.2,.2,.2,.2,.2] | ACC@1: 62.00 -> 64.53 | Helped |
| Use Lap-Top-k instead of SinkhornSort | ResNeXt-101 · ImageNet-1K, P_j=[0.,0,0,0,1.] | ACC@1: 85.65 -> 85.47 | Hurt |
| Use Lap-Top-k instead of SinkhornSort | ResNeXt-101 · ImageNet-21K-P, P_j=[0.,0,0,0,1.] | ACC@1: 36.93 -> 37.93 | Helped |
| Use Lap-Top-k instead of SinkhornSort | ResNeXt-101 · ImageNet-1K, P_j=[.5,0,0,0,.5] | ACC@5: 97.97 -> 97.93 | Hurt |
| Use Lap-Top-k instead of DiffSortNets | ResNeXt-101 · ImageNet-21K-P, P_j=[.5,0,0,0,.5] | ACC@5: 70.88 -> 71.05 | Helped |
| Use kNN+Lap-Top-k instead of kNN+NeuralSort | 2-layer CNN · MNIST | accuracy: 99.5 -> 99.4 | Hurt |
| Use kNN+Lap-Top-k instead of kNN+SOFT Top-k | ResNet18 · CIFAR-10 | accuracy: 92.6 -> 92.2 | Hurt |
| Use Lap instead of the strongest reported comparator | Large-MNIST soft-permutation method · Large-MNIST, n=3 | permutation accuracy: 93.0 -> 94.2 | Helped |
| Use Lap instead of the strongest reported comparator | Large-MNIST soft-permutation method · Large-MNIST, n=5 | permutation accuracy: 83.7 -> 85.3 | Helped |
| Use Lap instead of the strongest reported comparator | Large-MNIST soft-permutation method · Large-MNIST, n=7 | permutation accuracy: 74.1 -> 74.1 | No clear effect |
| Use Lap instead of the strongest reported comparator | Large-MNIST soft-permutation method · Large-MNIST, n=9 | permutation accuracy: 64.9 -> 63.1 | Hurt |
Surprising findings
- On Large-MNIST, the Lap method is worse than NeuralSort variants for larger n (n=9: 63.1 vs 64.9; n=15: 33.9 vs 41.8).
- Smooth top-k and NeuralSort vary widely across settings; SoftSort gets 1.01% ACC@1 on CIFAR-100 with top-5 one-hot targets.
Limitations
- Soft permutation accuracy trails NeuralSort at larger n (n=9, 15) on Large-MNIST.
- Top-k accuracy on ImageNet-1K is only on par with, not better than, competing methods.
- Some competing methods excluded from runtime comparisons due to failures or not returning probabilities.
Experimental setup
Datasets: CIFAR-100 ImageNet-1K ImageNet-21K-P MNIST CIFAR-10 Large-MNIST
Benchmarks: CIFAR-100 ImageNet-1K ImageNet-21K-P MNIST CIFAR-10 Large-MNIST
Metrics: ACC@1 ACC@5 permutation accuracy runtime peak memory approximation error of k
Baselines: Smooth top-k NeuralSort SoftSort SinkhornSort DiffSortNets Gumbel-Sinkhorn Optimal Transport Fast Differentiable Sparse Top-k (Dykstra)
Builds on: Fast differentiable top-k (Cuturi-style soft top-k / Petersen et al. difftopk) NeuralSort Sinkhorn sorting Gumbel-Sinkhorn
Closest papers by meaning
- Fast Differentiable Sorting and Ranking (ICML 2020 · similarity 0.86)
- PiRank: Scalable Learning To Rank via Differentiable Sorting (NeurIPS 2021 · similarity 0.86)
- ST$_k$: A Scalable Module for Solving Top-k Problems (NeurIPS 2024 · similarity 0.84)
- Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning (NeurIPS 2024 · similarity 0.83)
- Beyond Kemeny Medians: Consensus Ranking Distributions. Definition, Properties and Statistical Learning (NeurIPS 2026 · similarity 0.83)
- Transductive Conformal Inference for Full Ranking (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.