# Differentiable Ranks and Sorting using Optimal Transport

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

## Key facts

- Cited by 113 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 30 of 113)

- [Git Re-Basin: Merging Models modulo Permutation Symmetries](https://mlsanity.com/paper/2209.04836/) (2022)
- [LeJEPA: Provable and Scalable Self-Supervised Learning Without the Heuristics](https://mlsanity.com/paper/2511.08544/) (2025)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Equivariance with Learned Canonicalization Functions](https://mlsanity.com/paper/2211.06489/) (2022)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models](https://mlsanity.com/paper/2412.15287/) (2024)
- [Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems](https://mlsanity.com/paper/2505.15201/) (2025)
- [Differentiable Patch Selection for Image Recognition](https://mlsanity.com/paper/2104.03059/) (2021)
- [Deep Differentiable Logic Gate Networks](https://mlsanity.com/paper/2210.08277/) (2022)
- [GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection](https://mlsanity.com/paper/2103.17202/) (2021)
- [Training Uncertainty-Aware Classifiers with Conformalized Deep Learning](https://mlsanity.com/paper/2205.05878/) (2022)
- [Zero-TPrune: Zero-Shot Token Pruning through Leveraging of the Attention Graph in Pre-Trained Transformers](https://mlsanity.com/paper/2305.17328/) (2023)
- [Efficient Video Transformers with Spatial-Temporal Token Selection](https://mlsanity.com/paper/2111.11591/) (2021)
- [RankSim: Ranking Similarity Regularization for Deep Imbalanced Regression](https://mlsanity.com/paper/2205.15236/) (2022)
- [Enhancing Time Series Forecasting through Selective Representation Spaces: A Patch Perspective](https://mlsanity.com/paper/2510.14510/) (2025)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Adaptive Slot Attention: Object Discovery with Dynamic Slot Number](https://mlsanity.com/paper/2406.09196/) (2024)
- [Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision](https://mlsanity.com/paper/2105.04019/) (2021)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [A Large-Scale Study of Probabilistic Calibration in Neural Network Regression](https://mlsanity.com/paper/2306.02738/) (2023)
- [Provably Robust Conformal Prediction with Improved Efficiency](https://mlsanity.com/paper/2404.19651/) (2024)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Distributional Preference Alignment of LLMs via Optimal Transport](https://mlsanity.com/paper/2406.05882/) (2024)
- [Monotonic Differentiable Sorting Networks](https://mlsanity.com/paper/2203.09630/) (2022)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Multivariate Conformal Prediction using Optimal Transport](https://mlsanity.com/paper/2502.03609/) (2025)
- [Learning with Algorithmic Supervision via Continuous Relaxations](https://mlsanity.com/paper/2110.05651/) (2021)
- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)
- [An Information Theoretic Perspective on Conformal Prediction](https://mlsanity.com/paper/2405.02140/) (2024)

## Abstract (arXiv)

Sorting an array is a fundamental routine in machine learning, one that is used to compute rank-based statistics, cumulative distribution functions (CDFs), quantiles, or to select closest neighbors and labels. The sorting function is however piece-wise constant (the sorting permutation of a vector does not change if the entries of that vector are infinitesimally perturbed) and therefore has no gradient information to back-propagate. We propose a framework to sort elements that is algorithmically differentiable. We leverage the fact that sorting can be seen as a particular instance of the optimal transport (OT) problem on ℝ, from input values to a predefined array of sorted values (e.g. 1,2,dots,n if the input array has n elements). Building upon this link , we propose generalized CDFs and quantile operators by varying the size and weights of the target presorted array. Because this amounts to using the so-called Kantorovich formulation of OT, we call these quantities K-sorts, K-CDFs and K-quantiles. We recover differentiable algorithms by adding to the OT problem an entropic regularization, and approximate it using a few Sinkhorn iterations. We call these operators S-sorts, S-CDFs and S-quantiles, and use them in various learning settings: we benchmark them against the recently proposed neuralsort [Grover et al. 2019], propose applications to quantile regression and introduce differentiable formulations of the top-k accuracy that deliver state-of-the art performance.