In deep learning, we expect parameters to change smoothly: a tiny tweak to a weight should cause a tiny change in the loss. This smoothness is what allows backpropagation to work. However, many fundamental algorithmic operations are inherently discrete. Consider sorting a list of numbers or permuting a sequence of objects. If you have an input vector $x = [3.1, 1.2, 4.5]$, its sorted permutation matrix is a hard, binary assignment. If you perturb $x$ slightly to $[3.1, 1.21, 4.5]$, the output permutation matrix remains exactly the same. But if you change the second element enough to cross a threshold, the permutation matrix suddenly jumps to a completely different discrete state.
This behavior creates a nightmare for gradient-based optimization. The derivative of a discrete sorting operation with respect to its inputs is zero almost everywhere, and undefined at the boundaries where the jumps occur. If a neural network needs to learn how to sort, or if it needs to pass gradients through an ordering step to optimize an upstream component, standard backpropagation fails completely.
To bridge this gap, a powerful paradigm has emerged: differentiable permutation and sorting relaxations. By mapping discrete combinatorial operations into continuous, smooth spaces, researchers have made sorting and permuting fully compatible with gradient descent.
The Birkhoff Polytope and the Sinkhorn Operator
To understand how to relax a permutation, we must look at its geometric structure. A true permutation matrix is a square binary matrix where every row and every column sums to exactly 1. The space of all such matrices is discrete. However, if we relax the constraint that the entries must be strictly 0 or 1, and instead allow them to be any real number between 0 and 1, we get the space of doubly stochastic matrices.
Geometrically, the convex hull of all permutation matrices forms a geometric structure known as the Birkhoff polytope. The true, discrete permutations sit exactly at the vertices of this polytope. The goal of a continuous relaxation is to allow a neural network to operate inside the polytope during training, smoothly moving through the interior, and gradually pushing toward the sharp vertices as learning progresses.
Discrete Permutations (Vertices) Continuous Relaxation (Interior)
[1 0 0] [0.7 0.2 0.1]
[0 0 1] ======> [0.1 0.1 0.8]
[0 1 0] [0.2 0.7 0.0]
How do we map an arbitrary, real-valued matrix of predicted scores or affinities into this doubly stochastic space? The standard tool is the Sinkhorn operator. The Sinkhorn algorithm takes a square matrix and repeatedly applies a softmax function alternatingly across the rows and columns. Under mild conditions, this iterative normalization converges to a valid doubly stochastic matrix.
In Learning Latent Permutations with Gumbel-Sinkhorn Networks, Gonzalo E. Mena et al. introduced a temperature parameter $\tau$ to control this process. By dividing the input scores by $\tau$ before applying the Sinkhorn operator, the temperature acts as a tuning knob for softness:
- At high temperatures, the output matrix is smooth, blurry, and sits deep inside the interior of the Birkhoff polytope, allowing gradients to flow freely across all potential assignments.
- As $\tau \to 0$, the operator sharpens, forcing the matrix toward a hard, discrete permutation matrix at one of the vertices.
By adding Gumbel noise to the input scores before running the Sinkhorn iterations, the authors created a differentiable proxy for sampling permutations, providing a "Gumbel-Softmax for permutations" that allows models to reason about latent orderings end-to-end.
Differentiable Argsort: NeuralSort and SoftSort
While the Sinkhorn operator is excellent for matching and general permutations, many tasks specifically require sorting a sequence of scalar values. We need a differentiable version of the argsort operator—one that takes a vector of continuous scores and outputs a soft permutation matrix representing their relative ranks.
In Stochastic Optimization of Sorting Networks via Continuous Relaxations, Aditya Grover introduced NeuralSort. The core intuition relies on a mathematical identity: the $k$-th largest element in a set can be explicitly constructed by evaluating all pairwise absolute differences between elements. By replacing the non-differentiable argmax steps within this identity with a temperature-controlled softmax, the entire sorting operation becomes a smooth, continuous function. The output is a unimodal row-stochastic matrix where each row represents a probability distribution over which input element deserves that specific rank.
To make this process more computationally efficient, Julian Martin Eisenschlos et al. proposed SoftSort: A Continuous Relaxation for the argsort Operator. Instead of relying on complex pairwise identities, SoftSort constructs a soft permutation matrix by directly computing the distances between the unsorted input values and their sorted counterparts, passing these distances through a softmax function. This formulation achieves up to a 6x speedup over previous methods, making it highly scalable for deep architectures.
Why It Works: Applications Across Domains
By turning sorting and permuting into smooth, differentiable operations, researchers have unlocked solutions to a wide array of previously intractable combinatorial problems.
1. Enforcing Acyclicity in Graph Learning
Learning the structure of a Directed Acyclic Graph (DAG) from data is notoriously difficult because the space of graphs grows exponentially, and ensuring that a graph contains no cycles is a hard discrete constraint. However, a graph is a valid DAG if and only if there exists a topological ordering of its nodes such that edges only point from earlier nodes to later nodes.
By utilizing differentiable permutation relaxations, frameworks like those developed by Bertrand Charpentier et al. in Differentiable DAG Sampling and Chris Cundy et al. in BCD Nets can optimize over the continuous space of node orderings. Gradients can flow directly through the permutation layer to learn the topological layout, guaranteeing that the sampled graphs remain valid and cycle-free throughout the optimization process.
2. Direct Optimization of Ranking Metrics
In information retrieval and recommendation engines, models are evaluated using listwise metrics like Normalized Discounted Cumulative Gain (NDCG) or Average Precision (AP). Because these metrics depend entirely on the final sorted order of items, they are inherently non-differentiable. Historically, researchers had to settle for optimizing loose, pairwise proxy losses.
With continuous sorting relaxations, architectures like PiRank (Robin M. E. Swezey et al.) and RewardRank (Gaurav Bhatt et al.) can bypass proxies entirely. By substituting the discrete sorting step with operators like SoftSort, the evaluation metrics themselves become differentiable functions of the network's raw scoring parameters, allowing for direct, end-to-end listwise optimization.
3. Breaking Symmetries in Model Merging
Deep neural networks exhibit massive permutation symmetries: if you swap the order of two neurons in a hidden layer and adjust their corresponding incoming and outgoing weights, the network's mathematical function remains completely unchanged. This creates a problem when trying to average or merge two independently trained models, as their internal features are likely "scrambled" relative to one another.
To merge models successfully, one must find the optimal discrete permutation that aligns their hidden units. Samuel Ainsworth et al. in Git Re-Basin and Fidel A. Guerrero Peña et al. in Re-basin via implicit Sinkhorn differentiation demonstrated that this discrete matching problem can be relaxed using the Sinkhorn operator. This allows gradient descent to navigate the permutation space, smoothly aligning the neurons of disparate models until they reside in a single, shared loss basin where they can be safely combined.
4. Order-Invariant Set Representations
When a neural network processes a set of elements (where the input order shouldn't matter), it typically relies on global pooling operations like taking the mean or maximum. However, these operations act as an information bottleneck, destroying individual element identities and structural nuances.
To solve this "responsibility problem," Yan Zhang et al. developed FSPool: Learning Set Representations with Featurewise Sort Pooling and Learning Representations of Sets through Optimized Permutations. Instead of collapsing features, the network uses a differentiable sorting relaxation during training to dynamically arrange set elements into a canonical, sorted sequence. This transforms an unordered set into a structured sequence, allowing powerful downstream layers (like LSTMs or CNNs) to process the data without sacrificing permutation invariance.
Key Foundational Work
DeepPermNet: Visual Permutation Learning (2017) — contributed 2 concept elements to this direction.
Learning Representations of Sets through Optimized Permutations (2018) — contributed 2 concept elements to this direction.
Learning Latent Permutations with Gumbel-Sinkhorn Networks (2018) — contributed 4 concept elements to this direction.