Learning Unbiased Permutations via Flow Matching
Yimeng Min, Carla P. Gomes · 2026
Read Learning Unbiased Permutations via Flow Matching by Yimeng Min, Carla P. Gomes (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16755.txt.
Introduction
Min and Gomes present PermFlow, a flow-matching framework for learning permutations, which matter for sorting, ranking, and matching. Existing differentiable methods based on entropy-regularized Sinkhorn collapse to a single softened solution under ambiguity. PermFlow works directly on the affine subspace of matrices with unit row and column sums, using a closed-form projector that preserves constraints along every trajectory. A nearest-target coupling routes distinct noisy starts to distinct valid permutations. The model recovers both valid permutations under ambiguity and scores highly on unambiguous inputs.
Catalog record
| CREATOR | Yimeng Min, Carla P. Gomes |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52547 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16755
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Unbiased Permutations via Flow Matching Yimeng Min, Carla P. Gomes Abstract Learning permutations is fundamental to sorting, ranking, and matching, but existing differentiable methods based on entropy-regularized Sinkhorn produce a single softened solution and collapse under ambiguity. We present PermFlow, a conditional flow matching framework that operates directly on the affine subspace of matrices with unit row and column sums. A closed-form tangent-space projector preserves these constraints exactly along every trajectory, by construction rather than through iterative correction, and a nearest-target coupling routes distinct noisy initializations toward distinct valid permutations. The result is a model that captures multimodal permutation distributions rather than collapsing them to a single mode. On a visual sorting task with blended-digit ambiguity and a symmetric linear assignment problem, PermFlow achieves high accuracy on unambiguous inputs and recovers both valid permutations under ambiguity, where Sinkhorn-based baselines structurally fail. 1 Introduction Flow-based generative models have emerged as a powerful generative modeling paradigm, achieving widespread adoption across diverse domains such as computer vision and natural language processing. In these settings, the data lie in continuous spaces (e.g., high-dimensional vectors), where flows offer a principled mechanism for transforming simple noise into complex, structured outputs. Concretely, Flow Matching learns by regressing onto conditional velocity fields that transport individual samples; integrating this learned dynamics then yields a model capable of generating the full data distribution ( 3 ; 21 ; 6 ; 12 ; 20 ; 3 ) . However, this paradigm becomes significantly more challenging when we move to discrete combinatorial structures. Objects such as permutations, matchings, and tours obey strict structural constraints. For instance, a permutation matrix must contain exactly one “1” in each row and each column. As a result, these objects reside on highly constrained geometric spaces rather than in the unconstrained ambient space \mathbb{R}^{n\times n} , making the direct application of standard flow-based methods nontrivial. Most existing approaches deal with this difficulty by relaxing the problem. They replace permutations with continuous approximations (for example, using entropy-regularized Sinkhorn layers) and later round the solution back to a discrete one. While this makes optimization easier, it changes the geometry of the problem and can introduce bias or inconsistencies between training and testing. In particular, these methods usually produce a single softened solution and do not naturally represent uncertainty when multiple permutations are equally valid ( 19 ) . This is a real limitation in many settings where the supervision is set-valued rather than single-valued: there may be many feasible (and essentially equally good) permutations consistent with the input. For example, in matching or assignment problems with symmetries, repeated or indistinguishable items, or near-ties in cost, multiple permutations can explain the same observation. Yet a deterministic pipeline will still collapse everything into a single argmax permutation, committing to one choice and discarding alternative valid orderings. In contrast, what we often want is not one “best” permutation but a distribution over optimal permutations, allowing us to quantify ambiguity, sample diverse valid solutions, and propagate uncertainty downstream. Furthermore, entropy regularization introduces a well-known bias: the entropic term favors high-entropy solutions, pushing mass toward the interior of the Birkhoff polytope and away from permutation vertices. This alters the optimization landscape relative to the original combinatorial problem and, when combined with discrete rounding at inference time, leads to a mismatch between training and inference objectives ( 11 ) . In this work, we present Affine Permutation Flow (PermFlow). Instead of relaxing the structural constraints into an unconstrained continuous space, we directly design flow dynamics that respect the geometry of permutation matrices from the outset. We use Conditional Flow Matching (CFM) to learn velocity fields directly. By projecting the learned velocities onto the correct tangent space (which enforces zero row and column sums), we ensure that the structural constraints are preserved throughout training. This allows us to train flow-based models without relying on entropy regularization or ad hoc projection steps. Our approach generates a set of permutations by sampling different initial noise states and integrating the learned flow dynamics. As mentioned above, in many tasks, the correct ordering is inherently ambiguous, and multiple permutations may be equally consistent with the input. Unlike deterministic relaxations such as Sinkhorn, which collapse predictions to a single mode, our stochastic flow model captures this ambiguity by representing a distribution over permutations and sampling multiple valid combinatorial solutions ( 5 ; 17 ) . 2 Related Work The dominant paradigm for differentiable permutation prediction relaxes permutation matrices \mathcal{P} to the Birkhoff polytope \mathcal{B}_{+} via entropy-regularized optimal transport ( 18 ; 4 ) , with applications to latent permutation learning ( 17 ) , sorting ( 9 ) , and combinatorial RL ( 5 ) . The entropic term biases solutions toward the polytope interior ( 11 ) , and deterministic Sinkhorn cannot represent multimodal posteriors; Gumbel-Sinkhorn ( 17 ) adds noise but empirically concentrates around a single soft solution. Geometric alternatives include stick-breaking parameterizations of \mathcal{B}_{+} ( 13 ) and Riemannian Langevin sampling with retraction-based integrators ( 1 ) . We share the geometric viewpoint but work in the affine setting, which admits a closed-form orthogonal projector and removes the need for retractions, and we learn input-conditioned dynamics rather than fixed MCMC. Our construction builds on flow matching ( 14 ) and Conditional Flow Matching ( 21 ) , which have been extended to optimal-transport couplings ( 12 ) , Riemannian manifolds ( 3 ) , and discrete state spaces ( 2 ; 8 ) . By contrast, generic manifold-ODE schemes enforce constraints only approximately : under a Lipschitz assumption on the vector field, the violation is bounded by a factor growing as e^{Lt} in integration time and \mathcal{O}(h^{p}) in step size h , where L is the Lipschitz constant ( 10 ) . This exponential amplification carries over to learned vector fields, where projection or retraction steps are needed to keep iterates close to the constraint set ( 15 ; 7 ; 16 ; 3 ) , so feasibility degrades with both network expressivity (which controls L ) and integration horizon. Our contributions are threefold: 1. We propose a CFM framework for learning distributions over permutations. Our method parameterizes a velocity field directly on the affine subspace defined by the row- and column-sum constraints, and projects it onto the corresponding tangent space. As a result, these constraints hold exactly at every t and for any f_{\theta} , with no Lipschitz or smoothness assumption beyond ODE existence. This avoids entropic smoothing and explicit positivity constraints, in contrast to Sinkhorn-style relaxations whose feasibility only holds in the limit and to generic manifold-ODE schemes whose constraint violation grows as w.r.t. to time/iterations. 2. We apply the framework to ambiguous permutation prediction, where multiple orderings are equally consistent with the input. Sinkhorn and other deterministic relaxations collapse this ambiguity into a single solution. Our stochastic flow instead learns a conditional distribution over valid permutations, allowing explicit representation and sampling of multiple combinatorial modes. 3. Empirically, our model achieves competitive performance, showing that conditional flow matching can be extended beyond continuous domains such as vision and language to structured combinatorial objects. To our knowledge, this is one of the earliest applications of flow matching to inherently discrete permutation learning. 3 Background 3.1 Sinkhorn