# Reparameterizing the Birkhoff Polytope for Variational Permutation Inference

arXiv: https://arxiv.org/abs/1710.09508 · HTML: https://mlsanity.com/paper/1710.09508/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2017.

## Built on by (most cited first, 10 of 10)

- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Discovering Non-monotonic Autoregressive Orderings with Variational Inference](https://mlsanity.com/paper/2110.15797/) (2021)
- [Neural Topological Ordering for Computation Graphs](https://mlsanity.com/paper/2207.05899/) (2022)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)
- [Set-to-Sequence Methods in Machine Learning: a Review](https://mlsanity.com/paper/2103.09656/) (2021)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Differentiable Random Partition Models](https://mlsanity.com/paper/2305.16841/) (2023)
- [Variational phylogenetic inference with products over bipartitions](https://mlsanity.com/paper/2502.15110/) (2025)
- [Beyond Kemeny Medians: Consensus Ranking Distributions Definition, Properties and Statistical Learning](https://mlsanity.com/paper/2602.10640/) (2026)
- [Learning Unbiased Permutations via Flow Matching](https://mlsanity.com/paper/2605.16755/) (2026)

## Abstract (arXiv)

Many matching, tracking, sorting, and ranking problems require probabilistic reasoning about possible permutations, a set that grows factorially with dimension. Combinatorial optimization algorithms may enable efficient point estimation, but fully Bayesian inference poses a severe challenge in this high-dimensional, discrete space. To surmount this challenge, we start with the usual step of relaxing a discrete set (here, of permutation matrices) to its convex hull, which here is the Birkhoff polytope: the set of all doubly-stochastic matrices. We then introduce two novel transformations: first, an invertible and differentiable stick-breaking procedure that maps unconstrained space to the Birkhoff polytope; second, a map that rounds points toward the vertices of the polytope. Both transformations include a temperature parameter that, in the limit, concentrates the densities on permutation matrices. We then exploit these transformations and reparameterization gradients to introduce variational inference over permutation matrices, and we demonstrate its utility in a series of experiments.