  Query auto-completion (QAC) is a fundamental feature in search engines where
the task is to suggest plausible completions of a prefix typed in the search
bar. Previous queries in the user session can provide useful context for the
user's intent and can be leveraged to suggest auto-completions that are more
relevant while adhering to the user's prefix. Such session-aware QACs can be
generated by recent sequence-to-sequence deep learning models; however, these
generative approaches often do not meet the stringent latency requirements of
responding to each user keystroke. Moreover, these generative approaches pose
the risk of showing nonsensical queries.
  In this paper, we provide a solution to this problem: we take the novel
approach of modeling session-aware QAC as an eXtreme Multi-Label Ranking (XMR)
problem where the input is the previous query in the session and the user's
current prefix, while the output space is the set of tens of millions of
queries entered by users in the recent past. We adapt a popular XMR algorithm
for this purpose by proposing several modifications to the key steps in the
algorithm. The proposed modifications yield a 3.9x improvement in terms of Mean
Reciprocal Rank (MRR) over the baseline XMR approach on a public search logs
dataset. We are able to maintain an inference latency of less than 10 ms while
still using session context. When compared against baseline models of
acceptable latency, we observed a 33% improvement in MRR for short prefixes of
up to 3 characters. Moreover, our model yielded a statistically significant
improvement of 2.81% over a production QAC system in terms of suggestion
acceptance rate, when deployed on the search bar of an online shopping store as
part of an A/B test.
