# Assumption-free stability for ranking problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 2 Jun 2025.

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

- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Set-valued classification -- overview via a unified framework](https://mlsanity.com/paper/2102.12318/) (2021)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [Rank List Sensitivity of Recommender Systems to Interaction Perturbations](https://mlsanity.com/paper/2201.12686/) (2022)
- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Recommendation Systems with Distribution-Free Reliability Guarantees](https://mlsanity.com/paper/2207.01609/) (2022)
- [Building a stable classifier with the inflated argmax](https://mlsanity.com/paper/2405.14064/) (2024)
- [On Obtaining Stable Rankings](https://mlsanity.com/paper/1804.10990/) (2018)
- [Stability and Multigroup Fairness in Ranking with Uncertain Predictions](https://mlsanity.com/paper/2402.09326/) (2024)
- [Inference-time Stochastic Ranking with Risk Control](https://mlsanity.com/paper/2306.07188/) (2023)
- [FINEST: Stabilizing Recommendations by Rank-Preserving Fine-Tuning](https://mlsanity.com/paper/2402.03481/) (2024)

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

- [Stabilizing black-box algorithms through task-oriented randomization](https://mlsanity.com/paper/2606.25269/) (2026)
- [Feature Bagging Provides Stability](https://mlsanity.com/paper/2607.26964/) (2026)
- [Certification-Enhanced Generalization Bounds](https://mlsanity.com/paper/2610.06238/) (2026)

## Abstract (arXiv)

In this work, we consider ranking problems among a finite set of candidates: for instance, selecting the top-k items among a larger list of candidates or obtaining the full ranking of all items in the set. These problems are often unstable, in the sense that estimating a ranking from noisy data can exhibit high sensitivity to small perturbations. Concretely, if we use data to provide a score for each item (say, by aggregating preference data over a sample of users), then for two items with similar scores, small fluctuations in the data can alter the relative ranking of those items. Many existing theoretical results for ranking problems assume a separation condition to avoid this challenge, but real-world data often contains items whose scores are approximately tied, limiting the applicability of existing theory. To address this gap, we develop a new algorithmic stability framework for ranking problems, and propose two novel ranking operators for achieving stable ranking: the inflated top-k for the top-k selection problem and the inflated full ranking for ranking the full list. To enable stability, each method allows for expressing some uncertainty in the output. For both of these two problems, our proposed methods provide guaranteed stability, with no assumptions on data distributions and no dependence on the total number of candidates to be ranked. Experiments on real-world data confirm that the proposed methods offer stability without compromising the informativeness of the output.