# Counterfactual Learning To Rank for Utility-Maximizing Query Autocompletion

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

## Key facts

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

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Unbiased Learning-to-Rank with Biased Feedback](https://mlsanity.com/paper/1608.04468/) (2016)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Off-policy evaluation for slate recommendation](https://mlsanity.com/paper/1605.04812/) (2016)
- [Inferring Networks of Substitutable and Complementary Products](https://mlsanity.com/paper/1506.08839/) (2015)
- [A Hierarchical Recurrent Encoder-Decoder For Generative Context-Aware Query Suggestion](https://mlsanity.com/paper/1507.02221/) (2015)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [Hashing for Similarity Search: A Survey](https://mlsanity.com/paper/1408.2927/) (2014)
- [Personalized Language Model for Query Auto-Completion](https://mlsanity.com/paper/1804.09661/) (2018)
- [Learning to Attend, Copy, and Generate for Session-Based Query Suggestion](https://mlsanity.com/paper/1708.03418/) (2017)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [Efficient Neural Query Auto Completion](https://mlsanity.com/paper/2008.02879/) (2020)
- [Session-Aware Query Auto-completion using Extreme Multi-label Ranking](https://mlsanity.com/paper/2012.07654/) (2020)
- [Fast Label Embeddings for Extremely Large Output Spaces](https://mlsanity.com/paper/1503.08873/) (2015)
- [Unbiased Comparative Evaluation of Ranking Functions](https://mlsanity.com/paper/1604.07209/) (2016)
- [CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning](https://mlsanity.com/paper/1811.02672/) (2018)

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

- [LLM-Specific Utility for Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.11358/) (2025)
- [Recent Advances in the Foundations and Applications of Unbiased Learning to Rank](https://mlsanity.com/paper/2305.02914/) (2023)

## Abstract (arXiv)

Conventional methods for query autocompletion aim to predict which completed query a user will select from a list. A shortcoming of this approach is that users often do not know which query will provide the best retrieval performance on the current information retrieval system, meaning that any query autocompletion methods trained to mimic user behavior can lead to suboptimal query suggestions. To overcome this limitation, we propose a new approach that explicitly optimizes the query suggestions for downstream retrieval performance. We formulate this as a problem of ranking a set of rankings, where each query suggestion is represented by the downstream item ranking it produces. We then present a learning method that ranks query suggestions by the quality of their item rankings. The algorithm is based on a counterfactual learning approach that is able to leverage feedback on the items (e.g., clicks, purchases) to evaluate query suggestions through an unbiased estimator, thus avoiding the assumption that users write or select optimal queries. We establish theoretical support for the proposed approach and provide learning-theoretic guarantees. We also present empirical results on publicly available datasets, and demonstrate real-world applicability using data from an online shopping store.