Differentiable Ranking and Sorting via Continuous Relaxations

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2444 papers541 conceptsfrozen 2026-10-04

In standard deep learning, we are accustomed to optimizing continuous functions. We nudge weights, and the output nudges in response. However, many real-world problems—from search engines and recommendation systems to portfolio management—rely on sorting and ranking.

The problem is that sorting is fundamentally discrete. If you have a list of scores and you slightly increase the score of the third-place item, its rank remains "3" until it suddenly jumps to "2." In calculus terms, the derivative of the rank function is zero almost everywhere and undefined at the points where the order changes. This "staircase" behavior makes it impossible for gradients to flow back through a sorting operation, leaving rank-based objectives like Mean Average Precision (mAP) or Top-K accuracy "invisible" to backpropagation.

To solve this, researchers have developed differentiable relaxations that turn these discrete jumps into smooth, navigable slopes.

Sorting as Optimal Transport

One of the most elegant ways to make sorting differentiable is to reframe it as a geometry problem. marco cuturi, Olivier Teboul, and Jean-Philippe Vert in Differentiable Ranking and Sorting using Optimal Transport proposed treating sorting as an Optimal Transport (OT) problem.

Imagine you have a set of unsorted numbers (the source) and you want to map them to a set of sorted target positions (the destination). Sorting is simply the process of moving "mass" from the source to the destination with the minimum possible effort. By applying entropic regularization—a technique that adds a bit of "blurriness" to the transport plan—the discrete matching becomes a smooth, continuous mapping.

This allows the system to compute a "soft" version of ranks and sorted values. Instead of an item being strictly at rank 2, it might be 80% at rank 2 and 20% at rank 3. Because this "soft" assignment is computed using the Sinkhorn algorithm (which is just a series of matrix multiplications and divisions), it is fully differentiable. This enables models to optimize directly for things like median error or quantile regression, as seen in the OTT-JAX toolbox.

Soft Permutations and Rank Indicators

Another approach is to replace the discrete permutation matrix (a matrix of 0s and 1s) with a doubly stochastic matrix. In SoftSort: A Continuous Relaxation for the argsort Operator, Julian Martin Eisenschlos and Sebastian Prillo show that we can approximate the sorting of a vector by comparing all pairs of elements and using a softmax-like normalization.

This creates a "Soft Permutation" where every element has a fractional presence at every rank. As the "temperature" of the softmax decreases, this matrix converges to a true, discrete permutation. During training, a higher temperature provides smooth gradients that tell the model: "If you want this item to be ranked higher, you need to increase its score relative to these specific neighbors."

Similarly, Thibaut Thonet and Eric Gaussier introduced SmoothI, which uses a recursive masking mechanism. By calculating the probability of an item being at rank $k$ based on the probability that it wasn't selected for ranks $1$ through $k-1$, they create a differentiable bridge to Information Retrieval (IR) metrics like NDCG.

Why It Works: The Power of Relative Standing

The intuition behind why these methods work isn't just about "smoothing the curve." It's about changing the learning signal.

In a standard regression loss (like Mean Squared Error), the gradient for a single sample depends only on its absolute distance from a target value. In contrast, a differentiable ranking loss creates a gradient flow where an individual sample's update is a function of its relative standing among other samples in a batch.

As Yu Gong and Frederick Tung demonstrate with RankSim, this is incredibly powerful for imbalanced data. By forcing the model to align the ranking of neighbors in the feature space with their ranking in the label space, the model learns the structure of the data rather than just trying to memorize absolute values.

Applications Across Domains

The ability to "backprop through a sort" has unlocked several previously difficult tasks:

  • Computer Vision: Fangneng Zhan and colleagues use differentiable Top-K selection in RABIT to match style features between images, while Junke Wang uses it for token selection in video transformers.
  • Economics and Auctions: Xiangyu Liu and Chuan Yu developed Neural Auctions, where the entire auction mechanism—including the sorting of bids—is trained end-to-end to maximize revenue.
  • Resource Allocation: In public health, Kai Wang and Aditya Mate use differentiable ranking to optimize resource allocation in restless multi-armed bandits, ensuring that limited interventions are directed toward the most impactful cases.
  • Information Retrieval: Jiaguo Yu (in NSH) and Martin Engilberge (in SoDeep) show that training models to "naturally sort" or using neural proxies for sorting leads to significantly better retrieval performance by optimizing for the evaluation metric itself.

By treating sorting not as a fixed, discrete operation but as a smooth, learnable process, these researchers have bridged the gap between the structured logic of algorithms and the fluid optimization of deep learning.

Papers in this version

Showing 60 of 444 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 283 papers
  2. Version 1 · 2026-10-04 · 444 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_differentiable_ranking_approximation_8cfbcbf1,
  title = {differentiable ranking approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/differentiable-ranking-approximation/rdr_8cfbcbf197494572863f2e3af1b97309},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_differentiable_ranking_and_sorting_via_c_8cfbcbf1_v1,
  title = {Differentiable Ranking and Sorting via Continuous Relaxations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/differentiable-ranking-and-sorting-via-continuous-relaxations/rdr_8cfbcbf197494572863f2e3af1b97309/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}