Abstract
Conventional methods for query autocompletion (QAC) 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 QAC methods trained to mimic user behavior can lead to suboptimal query suggestions. To overcome this limitation, we propose a new approach that explicitly optimizes 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 leverages feedback on items (e.g., clicks, purchases) to evaluate query suggestions through an unbiased estimator, avoiding the assumption that users write or select optimal queries. We establish theoretical support and provide empirical results on public and real-world datasets, demonstrating significant improvements in search utility.
Introduction
Query Autocompletion (QAC) is a critical component of modern search interfaces, designed to assist users by suggesting completions for their partial search prefixes. Traditionally, these systems are optimized to maximize the probability of a user selecting a suggestion—essentially mimicking historical user behavior. However, this "mimicry" approach assumes that users are experts at navigating the search engine's index. In reality, users often select queries that lead to mediocre results because they are unaware of the specific keywords that would trigger the most relevant items.
This paper introduces a paradigm shift: instead of predicting what a user will type, QAC systems should suggest queries that lead to the best possible results. By focusing on the "utility" of the downstream search results, the system acts as an expert guide rather than a simple mirror of past behavior.
The Utility-Maximizing Framework
The authors formulate QAC as a "ranking of rankings" problem. In this framework, a prefix $x$ leads to a set of suggested queries $q \in \mathcal{Q}(x)$. Each query $q$, when executed, produces a ranked list of items $y_q$. The objective is to rank the queries $q$ such that the utility of the resulting item list $y_q$ is maximized.
Counterfactual Estimation
A significant challenge in training such a system is the reliance on historical log data, which is inherently biased. Users are more likely to click on items at the top of a list regardless of their actual relevance (position bias). To address this, the authors employ Inverse Propensity Scoring (IPS). By weighting observed interactions by the inverse of their observation probability (propensity), they create an unbiased estimator of the true utility of a query. This allows the model to learn from "noisy" clicks and identify high-utility queries that may have been overlooked in the past.
System Architecture
To handle the scale of modern search engines, the proposed system utilizes a two-stage pipeline:
- Retrieval Stage (PECOS): Given a prefix, the system must identify a candidate set of queries from a universe of millions. The authors use PECOS (Prediction for Enormous and Correlated Output Spaces), an extreme multi-label learning framework, to efficiently retrieve high-utility candidates in milliseconds.
- Re-ranking Stage (XGBoost): Once a candidate set is identified, a more complex model—specifically XGBoost using a Pairwise Learning to Rank (PLTR) objective—is used to fine-tune the ranking. This stage incorporates rich contextual features and the estimated utility scores derived from the counterfactual framework.
Empirical Evaluation
The researchers evaluated the utility-aware approach against standard baselines using two distinct datasets:
- LF-AmazonTitles-1.3M: This public dataset was used to simulate user logs with known click propensities. The proposed "Unbiased" method achieved a Utility@1 of 1.297, a nearly 30% improvement over the "Logged" baseline (1.000).
- Real-World E-commerce Data: Using anonymized logs from a major online store, the system demonstrated even more substantial gains. The utility-aware model achieved a Utility@1 of 1.979, nearly doubling the effectiveness of the baseline suggestions.
The experiments also confirmed the theoretical consistency of the model; as the volume of training data increased, the performance of the utility-aware ranker continued to improve, validating the generalization bounds established in the paper.
Discussion and Future Work
The shift from mimicry to utility-maximization represents a significant advancement in QAC research. One of the most compelling findings is the system's robustness: even when the propensity model (the mathematical description of user bias) is slightly mis-specified, the utility-aware approach still outperforms traditional methods.
However, several avenues for future research remain. The current model assumes additive utility, where the total value of a search result is the sum of its parts. Future iterations could explore sub-modular utility to better account for result diversity. Additionally, the strict latency requirements of QAC (often sub-100ms) continue to pose a challenge for deploying increasingly complex re-ranking models.
Conclusion
By treating query autocompletion as a gateway to downstream utility rather than a simple text-prediction task, this research provides a path toward more effective search experiences. The combination of counterfactual learning and scalable two-stage architectures allows for the creation of QAC systems that don't just follow the user, but actively lead them to the information they need.
Summary updated