Deep learning thrives on gradients. To optimize a neural network, we need to know how a tiny tweak to an internal parameter affects the final loss. But when a network needs to sort a list of items or optimize a rank-based metric like Mean Average Precision (mAP) or Normalized Discounted Cumulative Gain (NDCG), standard backpropagation hits a wall.
Sorting and ranking operations are fundamentally discrete. If we have a vector of model scores like $[0.8, 0.3, 0.6]$, their sorted ranks are $[3, 1, 2]$. If we perturb the first score slightly from $0.8$ to $0.81$, the ranks remain exactly $[3, 1, 2]$. Because a small change in the input produces zero change in the output, the derivative of the ranking function with respect to its inputs is exactly zero almost everywhere. At the precise moment two scores cross paths, the rank jumps discontinuously, making the gradient undefined.
As marco cuturi et al. point out in Differentiable Ranking and Sorting using Optimal Transport, this piecewise constant behavior creates an optimization black box. It prevents the direct integration of sorting logic into end-to-end architectures trained via gradient descent. To bridge this gap, researchers have developed techniques to relax these discrete operations into smooth, differentiable operators.
Continuous Relaxations and Soft Permutations
Mathematically, sorting a vector can be seen as multiplying it by a permutation matrix $P$—a discrete grid of $0$s and $1$s where each row and column contains exactly one $1$. To make sorting differentiable, we must relax this discrete matrix into a smooth, "soft" matrix.
Aditya Grover et al. introduced this concept with NeuralSort in Stochastic Optimization of Sorting Networks via Continuous Relaxations. They replaced the hard permutation matrix with a "unimodal row-stochastic matrix." In this relaxed matrix, elements are continuous values between $0$ and $1$ that sum to $1$. By controlling a temperature parameter, this soft matrix can smoothly transition from a completely uniform distribution during early training to a crisp, deterministic permutation at evaluation time.
Building on this, Julian Martin Eisenschlos et al. proposed SoftSort in SoftSort: A Continuous Relaxation for the argsort Operator. Instead of relaxing a full sorting network, the authors focused on the argsort operator directly, constructing a continuous relaxation based on the pairwise distances between all scores. This approach dramatically simplified the computation, making soft sorting faster and more scalable.
Another elegant perspective comes from optimal transport. The authors of Differentiable Ranking and Sorting using Optimal Transport noticed that sorting a vector of $n$ numbers is equivalent to finding the lowest-cost way to map those numbers onto a fixed, pre-sorted target grid (such as $[1, 2, \dots, n]$). By adding an entropic regularization term to this optimal transport problem, the objective becomes smooth and fully differentiable, allowing gradients to flow naturally via Sinkhorn iterations.
Neural Surrogates and Proxy Losses
Instead of rewriting the mathematical foundations of sorting, an alternative strategy is to train a separate neural network to mimic the sorting operation.
This is the core idea behind SoDeep, introduced by Martin Engilberge et al. in SoDeep: A Sorting Deep Net to Learn Ranking Loss Surrogates.. The authors pre-trained a dedicated LSTM network to take a vector of continuous scores and output their corresponding ranks. Because this proxy network is built from standard differentiable layers, it can be plugged directly into any deep learning pipeline as a loss function surrogate, allowing models to optimize directly for non-differentiable metrics like mAP or Spearman correlation.
Stochastic Gradient Estimation
Rather than smoothing the function itself, a third school of thought treats ranking as a probabilistic process. If we model the selection of an ordered list as a probability distribution, we can optimize the expected ranking metric using stochastic gradient estimators.
For instance, Harrie Oosterhuis explores this in Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness (Extended Abstract) by utilizing Plackett-Luce models. By exploiting the mathematical structure of these probability distributions, the author derived unbiased, low-variance gradient estimators that bypass the need to evaluate every possible permutation.
Similarly, Siamak Zamani Dadaneh et al. in ARSM Gradient Estimator for Supervised Learning to Rank leverage a discrete gradient estimator (ARSM) to backpropagate through categorical variables. This treats the final non-differentiable evaluation metric as a reward signal in a stochastic optimization framework, bypassing the need for a smooth surrogate altogether.
The Challenge of Vanishing Gradients
While differentiable ranking opens up powerful new capabilities—such as learning latent roles in team sports (Luca Scofano et al. in About Latent Roles in Forecasting Players in Team Sports)—it introduces a new challenge: vanishing gradients.
When we use smooth approximations like sigmoids or soft permutations, we often encounter flat regions in the loss landscape. As Yang Liu notes in Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrieval, if a pair of items is severely mis-ranked, naive smooth approximations can suffer from negligible gradients, preventing the model from learning how to correct major ordering errors.
To combat this, Xiao Pan in Dynamic gradient reactivation for backward compatible person re-identification proposed mechanisms like Dynamic Gradient Reactivation. These methods wake up dormant gradients in sharp activation functions, ensuring that both large ordering corrections and fine-grained ranking adjustments can continue throughout training.