Learning Permutation from Structure Without Supervision
2026-05-25 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how to find hidden orders in data, like sorting or solving puzzles, when the correct order is unknown. They improve a technique called Gumbel-Sinkhorn, which helps learn these orderings by approximating difficult math steps with softer versions. Unlike past methods that treated all parts of the problem equally, the authors let the method decide which parts it’s sure about and fix those early, while still exploring the uncertain parts. This smarter way makes learning more stable and accurate, especially for big or tricky problems.
Permutation matricesGumbel-SinkhornDifferentiable relaxationLatent operatorsEntropyTemperature parameterSorting algorithmsJigsaw puzzle reconstructionUnsupervised learningDoubly stochastic matrices
Authors
Ran Eisenberg, Ofir Lindenbaum
Abstract
Many learning problems require uncovering a hidden ordering that reveals structure in unordered data, such as monotonicity in sorting or spatial continuity in jigsaw reconstruction. In these settings, permutations can be learned as latent operators by optimizing objectives defined directly on the reordered output, often without access to ground-truth orderings. Differentiable relaxations such as Gumbel-Sinkhorn make this approach practical by approximating permutation matrices with doubly stochastic matrices. However, learning from structure without supervision induces a non-uniform uncertainty: some assignments become confident early, while others remain ambiguous. Existing methods control this process using a single global temperature, forcing all assignments to sharpen or diffuse simultaneously and leading to instability at scale. We introduce an entropy-adaptive formulation of Gumbel-Sinkhorn that locally modulates temperature based on assignment uncertainty. This allows confident assignments to discretize early while preserving exploration where uncertainty remains. Across sorting and jigsaw reconstruction tasks and in routing-style settings, adaptive entropy control improves training stability and final permutation quality relative to fixed-temperature baselines, particularly as problem size and assignment ambiguity increase.