# Stochastic Optimization of Sorting Networks via Continuous Relaxations

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

## Key facts

- Cited by 111 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2019.

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

- [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)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Unsupervised Learning of Group Invariant and Equivariant Representations](https://mlsanity.com/paper/2202.07559/) (2022)
- [Single Image Depth Estimation: An Overview](https://mlsanity.com/paper/2104.06456/) (2021)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision](https://mlsanity.com/paper/2105.04019/) (2021)
- [Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising](https://mlsanity.com/paper/2106.03593/) (2021)
- [Generalized Differentiable RANSAC](https://mlsanity.com/paper/2212.13185/) (2022)
- [A Large-Scale Study of Probabilistic Calibration in Neural Network Regression](https://mlsanity.com/paper/2306.02738/) (2023)
- [Ensuring User-side Fairness in Dynamic Recommender Systems](https://mlsanity.com/paper/2308.15651/) (2023)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance](https://mlsanity.com/paper/2306.02866/) (2023)
- [Monotonic Differentiable Sorting Networks](https://mlsanity.com/paper/2203.09630/) (2022)
- [Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning](https://mlsanity.com/paper/2104.09856/) (2021)
- [Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence](https://mlsanity.com/paper/2202.12183/) (2022)
- [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)
- [ProtoGate: Prototype-based Neural Networks with Global-to-local Feature Selection for Tabular Biomedical Data](https://mlsanity.com/paper/2306.12330/) (2023)
- [Structured Reordering for Modeling Latent Alignments in Sequence Transduction](https://mlsanity.com/paper/2106.03257/) (2021)
- [Softened Symbol Grounding for Neuro-symbolic Systems](https://mlsanity.com/paper/2403.00323/) (2024)
- [Discovering Non-monotonic Autoregressive Orderings with Variational Inference](https://mlsanity.com/paper/2110.15797/) (2021)
- [Self-Supervised Learning of Audio Representations from Permutations with Differentiable Ranking](https://mlsanity.com/paper/2103.09879/) (2021)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [Learning to Evict from Key-Value Cache](https://mlsanity.com/paper/2602.10238/) (2026)
- [Optimizing generalized Gini indices for fairness in rankings](https://mlsanity.com/paper/2204.06521/) (2022)
- [Learning by Sorting: Self-supervised Learning with Group Ordering Constraints](https://mlsanity.com/paper/2301.02009/) (2023)
- [LapSum -- One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection](https://mlsanity.com/paper/2503.06242/) (2025)

## Abstract (arXiv)

Sorting input objects is an important step in many machine learning pipelines. However, the sorting operator is non-differentiable with respect to its inputs, which prohibits end-to-end gradient-based optimization. In this work, we propose NeuralSort, a general-purpose continuous relaxation of the output of the sorting operator from permutation matrices to the set of unimodal row-stochastic matrices, where every row sums to one and has a distinct arg max. This relaxation permits straight-through optimization of any computational graph involve a sorting operation. Further, we use this relaxation to enable gradient-based stochastic optimization over the combinatorially large space of permutations by deriving a reparameterized gradient estimator for the Plackett-Luce family of distributions over permutations. We demonstrate the usefulness of our framework on three tasks that require learning semantic orderings of high-dimensional objects, including a fully differentiable, parameterized extension of the k-nearest neighbors algorithm.