# Learning-to-Rank at the Speed of Sampling: Plackett-Luce Gradient Estimation With Minimal Computational Complexity

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 26 references that are in the map.
- First posted on arXiv 22 Apr 2022.

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

- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness](https://mlsanity.com/paper/2105.00855/) (2021)
- [StochasticRank: Global Optimization of Scale-Free Discrete Functions](https://mlsanity.com/paper/2003.02122/) (2020)
- [Towards Meaningful Statements in IR Evaluation. Mapping Evaluation Measures to Interval Scales](https://mlsanity.com/paper/2101.02668/) (2021)

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

- [Towards Fair RAG: On the Impact of Fair Ranking in Retrieval-Augmented Generation](https://mlsanity.com/paper/2409.11598/) (2024)
- [On (Normalised) Discounted Cumulative Gain as an Off-Policy Evaluation Metric for Top-n Recommendation](https://mlsanity.com/paper/2307.15053/) (2023)
- [Probabilistic Rank and Reward: A Scalable Model for Slate Recommendation](https://mlsanity.com/paper/2208.06263/) (2022)
- [Practical and Robust Safety Guarantees for Advanced Counterfactual Learning to Rank](https://mlsanity.com/paper/2407.19943/) (2024)
- [Inference-time Stochastic Ranking with Risk Control](https://mlsanity.com/paper/2306.07188/) (2023)
- [Fast Slate Policy Optimization: Going Beyond Plackett-Luce](https://mlsanity.com/paper/2308.01566/) (2023)
- [Optimizing Group-Fair Plackett-Luce Ranking Models for Relevance and Ex-Post Fairness](https://mlsanity.com/paper/2308.13242/) (2023)
- [Proximal Ranking Policy Optimization for Practical Safety in Counterfactual Learning to Rank](https://mlsanity.com/paper/2409.09881/) (2024)
- [Estimating the Hessian Matrix of Ranking Objectives for Stochastic Learning to Rank with Gradient Boosted Trees](https://mlsanity.com/paper/2404.12190/) (2024)
- [Learning to Rank with Variable Result Presentation Lengths](https://mlsanity.com/paper/2506.23319/) (2025)
- [SeedER: Seed-Expand-Retrieve for Efficient Knowledge Graph Retrieval](https://mlsanity.com/paper/2605.23753/) (2026)
- [Exposure-Based Reinforcement Learning to Rank](https://mlsanity.com/paper/2607.18689/) (2026)
- [Structure-aware Relative Policy Optimization for Ranking](https://mlsanity.com/paper/2607.25268/) (2026)

## Abstract (arXiv)

Plackett-Luce gradient estimation enables the optimization of stochastic ranking models within feasible time constraints through sampling techniques. Unfortunately, the computational complexity of existing methods does not scale well with the length of the rankings, i.e. the ranking cutoff, nor with the item collection size. In this paper, we introduce the novel PL-Rank-3 algorithm that performs unbiased gradient estimation with a computational complexity comparable to the best sorting algorithms. As a result, our novel learning-to-rank method is applicable in any scenario where standard sorting is feasible in reasonable time. Our experimental results indicate large gains in the time required for optimization, without any loss in performance. For the field, our contribution could potentially allow state-of-the-art learning-to-rank methods to be applied to much larger scales than previously feasible.