# Learning Distributions over Permutations and Rankings with Factorized Representations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 30 May 2025.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [DiffusionBERT: Improving Generative Masked Language Models with Diffusion Models](https://mlsanity.com/paper/2211.15029/) (2022)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Neural Autoregressive Distribution Estimation](https://mlsanity.com/paper/1605.02226/) (2016)
- [Monotonic Differentiable Sorting Networks](https://mlsanity.com/paper/2203.09630/) (2022)
- [Revisit Recommender System in the Permutation Prospective](https://mlsanity.com/paper/2102.12057/) (2021)
- [DiSK: A Diffusion Model for Structured Knowledge](https://mlsanity.com/paper/2312.05253/) (2023)
- [SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups](https://mlsanity.com/paper/2410.02942/) (2024)
- [Generalized Neural Sorting Networks with Error-Free Differentiable Swap Functions](https://mlsanity.com/paper/2310.07174/) (2023)
- [Entropy Coding of Unordered Data Structures](https://mlsanity.com/paper/2408.08837/) (2024)

## Abstract (arXiv)

Learning distributions over permutations is a fundamental problem in machine learning, with applications in ranking, combinatorial optimization, structured prediction, and data association. Existing methods rely on mixtures of parametric families or neural networks with expensive variational inference procedures. In this work, we propose a novel approach that leverages alternative representations for permutations, including Lehmer codes, Fisher-Yates draws, and Insertion-Vectors. These representations form a bijection with the symmetric group, allowing for unconstrained learning using conventional deep learning techniques, and can represent any probability distribution over permutations. Our approach enables a trade-off between expressivity of the model family and computational requirements. In the least expressive and most computationally efficient case, our method subsumes previous families of well established probabilistic models over permutations, including Mallow's and the Repeated Insertion Model. Experiments indicate our method significantly outperforms current approaches on the jigsaw puzzle benchmark, a common task for permutation learning. However, we argue this benchmark is limited in its ability to assess learning probability distributions, as the target is a delta distribution (i.e., a single correct solution exists). We therefore propose two additional benchmarks: learning cyclic permutations and re-ranking movies based on user preference. We show that our method learns non-trivial distributions even in the least expressive mode, while traditional models fail to even generate valid permutations in this setting.