# Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 10 Jul 2025.

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

- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Algorithmic Monoculture and Social Welfare](https://mlsanity.com/paper/2101.05853/) (2021)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [MallowsPO: Fine-Tune Your LLM with Preference Dispersions](https://mlsanity.com/paper/2405.14953/) (2024)
- [Efficiently Learning Mixtures of Mallows Models](https://mlsanity.com/paper/1808.05731/) (2018)
- [Optimal Learning of Mallows Block Model](https://mlsanity.com/paper/1906.01009/) (2019)
- [A Bayesian Bradley-Terry model to compare multiple ML algorithms on multiple data sets](https://mlsanity.com/paper/2208.04935/) (2022)
- [Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments](https://mlsanity.com/paper/2009.06784/) (2020)
- [On A Mallows-type Model For (Ranked) Choices](https://mlsanity.com/paper/2207.01783/) (2022)
- [FPRAS Approximation of the Matrix Permanent in Practice](https://mlsanity.com/paper/2012.03367/) (2020)

## Abstract (arXiv)

textitMallows model is a widely-used probabilistic framework for learning from ranking data, with applications ranging from recommendation systems and voting to aligning language models with human preferences~citechen2024mallows, kleinberg2021algorithmic, rafailov2024direct. Under this model, observed rankings are noisy perturbations of a central ranking σ, with likelihood decaying exponentially in distance from σ, i.e, P (π) propto expbig(-β · d(π, σ)big), where β > 0 controls dispersion and d is a distance function. Existing methods mainly focus on fixed distances (such as Kendall's τ distance), with no principled approach to learning the distance metric directly from data. In practice, however, rankings naturally vary by context; for instance, in some sports we regularly see long-range swaps (a low-rank team beating a high-rank one), while in others such events are rare. Motivated by this, we propose a generalization of Mallows model that learns the distance metric directly from data. Specifically, we focus on Lα distances: dα(π,σ):=sumi=1 |π(i)-σ(i)|α. For any α≥ 1 and β>0, we develop a Fully Polynomial-Time Approximation Scheme (FPTAS) to efficiently generate samples that are ε- close (in total variation distance) to the true distribution. Even in the special cases of L1 and L2, this generalizes prior results that required vanishing dispersion (β→0). Using this sampling algorithm, we propose an efficient Maximum Likelihood Estimation (MLE) algorithm that jointly estimates the central ranking, the dispersion parameter, and the optimal distance metric. We prove strong consistency results for our estimators (for any values of α and β), and we validate our approach empirically using datasets from sports rankings.