Standard deep learning thrives on continuity. We optimize neural networks by nudging weights along a smooth loss landscape. However, many fundamental problems—sorting a list, matching objects across video frames, or aligning the neurons of two different models—are inherently discrete. These tasks require finding a permutation, a one-to-one mapping that reorders elements.
Because permutations are discrete, they are "gradient-blind." You cannot slightly adjust a permutation; you either swap elements or you don't. This discreteness creates a bottleneck for end-to-end learning. To solve this, a growing body of research focuses on relaxing discrete permutations into continuous, differentiable operators, primarily through the use of the Sinkhorn algorithm.
The Birkhoff Polytope and Soft Permutations
A discrete permutation of $n$ elements can be represented by a permutation matrix: a square matrix of 0s and 1s where each row and column sums to exactly one. The space of all such matrices is discrete and difficult to optimize over.
To make this space differentiable, researchers like Gonzalo E. Mena in Learning Latent Permutations with Gumbel-Sinkhorn Networks propose relaxing these matrices into doubly stochastic matrices. These matrices live in the Birkhoff polytope, a continuous "convex hull" where entries can be any value between 0 and 1, provided the row and column sums remain one.
The bridge to this space is the Sinkhorn operator. By taking any square matrix with positive entries and iteratively normalizing its rows and columns, the Sinkhorn algorithm converges to a doubly stochastic matrix. Because this iterative process is differentiable, it allows gradients to flow from a discrete-like "soft permutation" back into the neural network that generated the initial scores.
Unscrambling the Latent Basin
One of the most striking applications of this idea is in model merging. Even if two neural networks have the same architecture and were trained on the same data, their weights will look completely different because the neurons in each layer can be permuted without changing the model's output.
In Git Re-Basin: Merging Models modulo Permutation Symmetries, Samuel Ainsworth and colleagues demonstrate that these models actually reside in the same "loss basin." By using differentiable permutations to "unscramble" the neurons of one model to match another, they show you can merge two different models by simply averaging their weights. This concept is extended by Akira Ito in Linear Mode Connectivity between Multiple Models modulo Permutation Symmetries, which uses a Straight-Through Estimator (STE) to align multiple models simultaneously, revealing a shared convex region in the weight space.
Discovering Causal and Temporal Order
Beyond aligning weights, differentiable permutations allow models to "discover" the optimal order of data. In causal discovery, the goal is to find the directed acyclic graph (DAG) that explains the relationships between variables. This is essentially a sorting problem: what is the causal ordering of nodes?
Yashas Annadani and the team behind BayesDAG use the Sinkhorn operator to relax the sorting of nodes, allowing them to sample valid DAGs using gradient-based MCMC. Similarly, Arash Mehrjou in Efficient Differentiable Discovery of Causal Order uses DiffIntersort to transform discrete variable ordering into a continuous optimization problem, enabling causal structures to be learned directly from interventional data via backpropagation.
This "learning to order" also applies to time-series. Shivam Grover argues in Segment, Shuffle, and Stitch that the chronological order of data isn't always optimal for representation learning. By backpropagating through a shuffling operation, their model learns to rearrange data segments to highlight the most important temporal relationships.
Solving Combinatorial Puzzles
The most direct use of these networks is in solving NP-hard combinatorial problems. Traditionally, problems like the Traveling Salesman Problem (TSP) or the Quadratic Assignment Problem (QAP) required expensive search algorithms.
Carla P Gomes and Yimeng Min have pioneered a "search-free" approach. In Structure As Search and Unsupervised Learning for Quadratic Assignment, they use Gumbel-Sinkhorn operators to minimize combinatorial objectives directly. By treating the permutation as a latent variable, the network learns to output optimal tours or assignments in a single forward pass.
This same logic allows Gaël Heck to solve jigsaw puzzles with vision transformers. Instead of classifying where each piece goes, the model predicts an affinity matrix that the Sinkhorn algorithm refines into a soft permutation, allowing the model to "reason" about the global layout of the image.
Why It Works: The Intuition of Global Constraints
The power of the Sinkhorn-based approach lies in its global enforcement of constraints. In a standard classification setup, a model might predict that two different image patches both belong in the "top-left" corner. A Sinkhorn layer prevents this. Because it forces the matrix to be doubly stochastic, it effectively tells the model: "If you put Patch A here, you must put Patch B somewhere else."
By turning a set of independent local decisions into a single global assignment problem, differentiable permutation learning allows neural networks to respect the fundamental "one-to-one" nature of the physical and logical world. Whether it is matching markers in motion capture (Ali Etemad, Auto-labelling of Markers) or reordering channels for sparse LLMs (Lancheng Zou, PermLLM), the core intuition remains the same: relax the discrete, enforce the global, and let the gradients do the rest.