🤖 machine learning

Learning Permutation from Structure Without Supervision

This paper introduces an entropy-adaptive Gumbel-Sinkhorn formulation that locally modulates temperature based on assignment uncertainty to improve training stability and permutation quality in unsupervised learning tasks involving hidden orderings, overcoming the limitations of global temperature control in large-scale problems.

Original authors: Ran Eisenberg, Ofir Lindenbaum

Published 2026-05-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ran Eisenberg, Ofir Lindenbaum

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy pile of puzzle pieces, or a shuffled deck of cards, or a list of numbers in random order. Your goal is to put them back in the right order. But here's the catch: you don't have the picture on the box, and you don't have the answer key. You only know that once the pieces are in the right place, the picture will look smooth, the cards will be sorted, or the numbers will go from small to big.

This is the problem the paper tackles: How do you teach a computer to find the right order when it has to guess based only on the "vibe" of the final result?

The Old Way: The "One-Size-Fits-All" Thermostat

To solve this, computers use a mathematical trick called Gumbel-Sinkhorn. Think of this as a way to let the computer "try out" different orders without getting stuck.

In the old method, the computer uses a single control knob called temperature.

High Temperature: The computer is very "confused." It tries many different arrangements, keeping its options open. It's like a student who is still brainstorming and hasn't decided on an answer yet.
Low Temperature: The computer becomes "decisive." It picks one specific arrangement and sticks to it.

The problem with the old method is that it uses one single thermostat for the whole room.

If you turn the heat down to make the computer decisive, everything becomes decisive at once.
But in reality, some parts of the puzzle are easy to solve (like the corner pieces), while others are very hard (like a patch of blue sky that looks the same everywhere).
If you force the computer to be decisive too early, it locks in mistakes on the hard parts. If you keep it confused too long, it never finishes the easy parts. It's a frustrating balancing act.

The New Way: The "Smart Thermostat"

The authors of this paper introduced a new method called Entropy-Adaptive Gumbel-Sinkhorn. Instead of one thermostat for the whole room, they gave the computer a smart, multi-zone thermostat that looks at every single piece of the puzzle individually.

Here is how it works using a simple analogy:

Imagine you are organizing a chaotic library.

The Easy Aisle (Low Uncertainty): You see a row of books that are clearly out of place. You know exactly where they go.
- Old Method: The thermostat says, "Wait, let's keep thinking!" and keeps the whole library in a state of confusion.
- New Method: The smart thermostat sees this aisle is clear and says, "Great, lock this aisle in place immediately!" It stops wasting time here.
The Hard Aisle (High Uncertainty): You see a section of books that all look identical. You aren't sure which one goes where.
- Old Method: The thermostat says, "Okay, let's lock everything in place now," forcing you to guess on these identical books. You likely get it wrong.
- New Method: The smart thermostat sees the confusion and says, "Hold on, this area is tricky. Keep exploring different options here. Don't lock it in yet."

What Did They Find?

The researchers tested this "Smart Thermostat" on three different tasks:

Sorting Numbers: Putting a list of numbers in order.
Jigsaw Puzzles: Reassembling a scrambled image.
The Traveling Salesman: Finding the shortest route to visit many cities.

The Results:

When the problems were small and easy, the new method worked about the same as the old one.
But when the problems got big and confusing, the old method started to fail. It either got stuck on mistakes or couldn't find a solution.
The new method was much better. It successfully solved the easy parts quickly while keeping the hard parts flexible until it found the right answer. It was more stable and produced higher-quality results, especially as the puzzles got larger.

The Bottom Line

The paper doesn't claim this will solve every problem in the world, but it solves a specific headache in machine learning: How to handle situations where some parts of a problem are easy and others are hard.

By letting the computer be decisive where it's sure and curious where it's unsure, they made the process of learning from structure much more reliable, without needing a human to tell them the answer beforehand.

Technical Summary: Learning Permutation from Structure Without Supervision

Problem Statement

Many learning tasks involve data that is naturally unordered at observation time, requiring the recovery of a hidden permutation to reveal underlying structure. Examples include sorting (recovering monotonicity), jigsaw reconstruction (recovering spatial continuity), and routing problems like the Traveling Salesman Problem (TSP). In these settings, ground-truth permutations are often unavailable, necessitating unsupervised learning driven by task-specific structural properties (e.g., smoothness, monotonicity, or geometric coherence) rather than direct label supervision.

Recent advances in differentiable permutation learning, particularly the Gumbel–Sinkhorn method, allow permutations to be treated as latent operators optimized via continuous relaxations. These methods approximate discrete permutation matrices using doubly stochastic matrices within the Birkhoff polytope, controlled by a global temperature parameter $\tau$ (or inverse temperature $\beta$ ). However, a critical limitation arises as problem size and ambiguity increase: different parts of the assignment matrix resolve at different rates. Some rows/columns become deterministic early in training, while others remain ambiguous due to symmetry or weak structural cues. A single global temperature forces all assignments to sharpen or diffuse simultaneously, creating an unavoidable trade-off between stability and discretization. Aggressive annealing locks in early errors, while conservative annealing prevents large, ambiguous permutations from converging.

Methodology

The authors propose an entropy-adaptive formulation of Gumbel–Sinkhorn that replaces the single global temperature with a locally varying, row- and column-dependent inverse-temperature field. This approach modulates the temperature based on the uncertainty of the current soft permutation assignment.

Core Mechanism

Entropy Estimation: At each training step, a deterministic soft assignment $Q$ is computed using a base inverse temperature $\beta_0(t)$ :
$Q = \text{Sinkhorn}(\beta_0(t) \cdot \text{stopgrad}(S))$
where $S$ represents the compatibility scores. The stop-gradient ensures the entropy controller does not backpropagate through the temperature estimation itself.
Uncertainty Calculation: Normalized row and column entropies ( $H^{\text{row}}_i$ and $H^{\text{col}}_j$ ) are computed from $Q$ . Values near zero indicate confident assignments, while values near one indicate high uncertainty.
Adaptive Temperature Field: An entrywise inverse-temperature field $\beta \in \mathbb{R}^{n \times n}$ is constructed. For high-entropy rows or columns, the inverse temperature is reduced (increasing the effective temperature) to preserve exploration. For low-entropy regions, the inverse temperature remains at the base level to encourage discretization.
$\beta^{\text{row}}_i = \frac{\beta_0(t)}{1 + b(H^{\text{row}}_i)}, \quad \beta^{\text{col}}_j = \frac{\beta_0(t)}{1 + b(H^{\text{col}}_j)}$
where $b(\cdot)$ is a bounded, monotone function that activates only when entropy exceeds a threshold $H_0$ . The final entrywise field is the average: $\beta_{ij} = \frac{1}{2}(\beta^{\text{row}}_i + \beta^{\text{col}}_j)$ .
Sampling: The final soft permutation $P$ is sampled using this adaptive field:
$P = \text{Sinkhorn}(\beta \odot (S + g))$
where $g$ is Gumbel noise and $\odot$ denotes elementwise multiplication.

Theoretical Interpretation

The paper establishes that applying Sinkhorn normalization with an entrywise inverse-temperature field is equivalent to solving an entropically regularized assignment problem with locally rescaled costs. This provides an optimal transport interpretation where adaptive temperature control delays symmetry breaking in ambiguous regions while allowing confident regions to concentrate, all while maintaining global doubly stochastic constraints.

Key Contributions

Unified Framework: A framework for learning permutations as latent operators directly from task-specific structural losses on reordered data, enabling unsupervised learning without ground-truth permutations.
Entropy-Adaptive Gumbel–Sinkhorn: A novel variant that replaces global temperature with a locally varying field derived from assignment entropy. This allows confident assignments to discretize early while preserving exploration in ambiguous regions.
Optimal Transport Interpretation: A proof that adaptive temperature control is equivalent to local cost rescaling over the Birkhoff polytope, offering a theoretical foundation for the method's behavior.
Empirical Validation: Demonstration across sorting, jigsaw reconstruction, and unsupervised TSP that entropy-adaptive control yields more reliable convergence and higher-quality permutations than fixed or globally annealed baselines, particularly as problem size ( $n$ ) and assignment ambiguity increase.

Experimental Results

The method was evaluated on three primary tasks:

List Sorting: On datasets with high ambiguity (values in $[10, 11]$ ), entropy-adaptive temperature consistently outperformed global annealing and NeuralSort. As $n$ increased to 300, the performance gap widened, with the adaptive method maintaining significantly higher Kendall $\tau$ scores.
Jigsaw Reconstruction: On CelebA-Test images partitioned into grids (up to $7 \times 7$ ), the adaptive method achieved higher Kendall $\tau$ and more stable convergence across random seeds compared to global annealing. Improvements were most pronounced for larger puzzles where boundary consistency cues are ambiguous.
Unsupervised TSP: Applied to the UTSP protocol, the method (using a degree-violation-based adaptation variant) reduced tour lengths and optimality gaps compared to standard Gumbel–Sinkhorn and UTSP baselines, particularly for larger node counts ( $n=500, 1000$ ).

In all cases, the adaptive method demonstrated robustness to hyperparameter choices (entropy threshold $H_0$ and max boost $b_{\text{max}}$ ) and avoided the instability associated with global temperature schedules in high-ambiguity regimes.

Significance and Claims

The paper claims that effective permutation learning from structure depends critically on managing where and when entropy collapses during optimization. By acknowledging that assignment uncertainty is heterogeneous, the proposed method resolves the stability-discretization trade-off inherent in global temperature schedules.

The authors position this work as a lightweight extension to the Gumbel–Sinkhorn family that improves scalability and stability without altering the underlying relaxation geometry or convergence properties. They note that while the method improves optimization stability, it does not resolve fundamental ambiguities in highly symmetric or weakly informative objectives, and some form of symmetry breaking (e.g., anchor tiles in jigsaw puzzles) may still be required.

Future directions suggested include learning the entropy-adaptive control end-to-end and extending uncertainty-aware discretization to more complex combinatorial structures and multimodal matching problems.