Introduction
Sorting input objects is a fundamental step in many machine learning pipelines, from search engine ranking to $k$-nearest neighbors (kNN) classification. However, the standard sorting operator is inherently discrete and non-differentiable. If you change the input values slightly, the sorted order remains identical until it suddenly jumps to a new configuration. This "jumpiness" means gradients are zero almost everywhere, prohibiting the use of backpropagation to train models end-to-end if they include a sorting step.
To solve this, researchers introduce NeuralSort, a general-purpose, continuous relaxation of the sorting operator. By replacing discrete permutation matrices with continuous approximations, NeuralSort enables neural networks to learn semantic orderings of complex data through standard gradient-based optimization.
The Core Method: Relaxing the Sort
Previously, researchers relied on noisy "straight-through" estimators or relaxations like the Sinkhorn operator, which are better suited for matching problems than sorting. NeuralSort provides a more principled approach using two main components:
1. Continuous Relaxation
The authors leverage a mathematical identity that expresses the $k$-th largest element in a set based on absolute pairwise differences. By replacing the discrete argmax in this identity with a continuous softmax (controlled by a temperature parameter $\tau$), they transform the output into a "unimodal row-stochastic matrix." As the temperature $\tau$ approaches zero, this relaxed matrix converges to a standard, discrete permutation matrix.
2. Stochastic Optimization
To handle uncertainty and explore different rankings during training, NeuralSort is extended to distributions over permutations—specifically the Plackett-Luce family.
The authors employ a "reparameterization trick" akin to the Gumbel-Softmax trick. By adding Gumbel noise to the input scores before applying the NeuralSort operator, the model can sample different permutations while remaining fully differentiable. This allows gradients to flow smoothly back to the network parameters.
Key Insight: The Importance of Unimodality
A major theoretical contribution of NeuralSort is its focus on unimodality.
Unlike previous relaxations (such as Sinkhorn) that produce "doubly-stochastic" matrices, NeuralSort produces "unimodal" matrices. In a unimodal matrix, every row has a distinct maximum value. This property is crucial because it makes it significantly easier to "project" the continuous, relaxed matrix back into a hard, discrete sorting order for final evaluation or downstream tasks.
Applications and Results
The paper evaluates NeuralSort across several tasks that require learning semantic orderings of high-dimensional objects:
- Sorting as a Representation Learner: The authors created a
large-MNISTbenchmark by concatenating four MNIST digits to form 4-digit numbers (e.g., images of "1", "8", "1", "0" form 1810). The model had to learn the semantic value of the images to sort them. For sequences of 15 images, NeuralSort achieved ~40% exact match accuracy (correctly identifying the entire permutation), whereas traditional relaxations like Sinkhorn failed entirely (0% accuracy). - Quantile Regression: When tasked with predicting the median value of a sequence of images, a network equipped with NeuralSort achieved a Mean Squared Error (MSE) nearly 10x lower than a standard vanilla neural network.
- Differentiable kNN: Traditionally, kNN is a fixed algorithm. By making the "top-k" selection differentiable, NeuralSort enables a kNN classifier to train its own feature extractor (a CNN) end-to-end. On CIFAR-10, this Differentiable kNN reached 90.7% accuracy, outperforming standard kNN and PCA-based kNN, and approaching the performance of a pure CNN (95.1%) while preserving the interpretability of a nearest-neighbor approach.
Limitations and Future Directions
While powerful, NeuralSort has a few limitations:
- Computational Complexity: The operator requires $O(n^2)$ operations due to the calculation of pairwise differences between all $n$ elements. While highly parallelizable on modern GPUs, it is theoretically slower than the $O(n \log n)$ complexity of standard sorting algorithms.
- Temperature Sensitivity: Like many continuous relaxations, performance is sensitive to the temperature parameter $\tau$. High temperatures yield smoother gradients but coarser approximations, while low temperatures are more accurate but risk vanishing gradients.
Looking forward, the authors suggest this framework could be applied to other discrete structures, such as relaxing beam search in natural language processing or tackling broader combinatorial optimization problems.
Summary updated