Query Autocompletion

Every keystroke in a search box is a request. A user typing "fantasy football rankings" at a normal pace sends two dozen prefixes in a few seconds, and each response has to arrive before the next key does or the suggestions flicker and are ignored. Query autocompletion (QAC) is therefore a ranking problem with an unusually tight budget and an unusually short query: at two characters, the prefix is compatible with millions of past queries.

It is also a query-understanding component in disguise. A suggestion the user accepts replaces what they would have typed, so autocompletion shapes the query distribution the rest of the search stack sees, fixing spelling and steering phrasing before retrieval ever runs.

The baseline that is hard to beat

The standard baseline is most popular completion (MPC). Given prefix \(p\) and a log of past queries with frequencies \(f(q)\), return the top \(k\) of

Bar-Yossef and Kraus used this popularity baseline and showed where it fails: for one- or two-character prefixes the most popular completions are poor guesses about a particular user, and their NearestCompletion method, which ranks completions by similarity to the user's recent queries, improved prediction considerably even at those short prefixes (Bar-Yossef and Kraus, 2011, Context-Sensitive Query Auto-Completion, WWW).

A worked example shows why MPC is strong anyway. Suppose the prefix "fa" matches facebook (900,000 past queries), fantasy football (300,000) and fandango (120,000). MPC shows them in that order. If the next user is equally likely to be any past user, then showing facebook first is the ranking that maximises the expected reciprocal rank of the intended query. Any personalised model has to beat that expected value, and on head prefixes it often cannot by much.

Serving it in microseconds

Computing \(C(p)\) and sorting at query time is hopeless for short prefixes. The classic structure is a trie in which each node stores the maximum score in its subtree. Top-\(k\) completion then becomes a best-first search: start at the node for \(p\), push children onto a priority queue keyed by their subtree maximum, and pop until \(k\) complete queries have been emitted. Only nodes that can contain a top-\(k\) result are ever expanded.

Hsu and Ottaviano engineered this for scale. Aiming at sets of hundreds of millions of queries, their three trie variants compress the strings and scores to sizes competitive with gzip while returning completions in about a microsecond each (Hsu and Ottaviano, 2013, Space-Efficient Data Structures for Top-k Completion, WWW). They also note why the obvious shortcut fails: precomputing the top \(k\) for every short prefix needs \(k\) fixed in advance and its space grows badly with \(k\). The skew of query frequencies, a power law in which most queries are rare, is what makes the scores cheap to compress.

Beyond popularity

Cai and de Rijke's survey organises the literature into time-sensitive approaches, which track how popularity shifts by hour, season and news event, and user-centred approaches, which use the searcher's history and context (Cai and de Rijke, 2016, A Survey of Query Auto Completion in Information Retrieval, Foundations and Trends in IR 10(4)). Shokouhi's supervised ranker with demographic and search-history features improved MRR by up to 9 percent over popularity baselines (Shokouhi, 2013, Learning to Personalize Query Auto-Completion, SIGIR).

The harder problem is the prefix with no history. Mitra and Craswell generated synthetic candidates for rare prefixes by attaching popular query suffixes mined from the logs, then ranked those candidates with learned features (Mitra and Craswell, 2015, Query Auto-Completion for Rare Prefixes, CIKM). Generative models extend that idea to any prefix. On AmazonQAC, 395 million prefix-query samples from Amazon search logs, fine-tuned LLMs with session context performed best, yet reached only about half of the theoretical maximum on the test data (Everaert, Patki, Zheng and Potts, 2024, AmazonQAC: A Large-Scale, Naturalistic Query Autocomplete Dataset, EMNLP, arXiv:2411.04129).

Practitioners disagree about the trade. Log-based completion can only suggest queries someone has issued, which is a safety property; generative completion covers the tail and can suggest a fluent query that returns nothing, at the cost of a model call on every keystroke.

When it breaks

Suggestions put words in people's mouths. Olteanu, Diaz and Kazai showed that completions can be perceived as biased, offensive or harmful, reinforcing stereotypes and nudging users toward what they had not intended to search (Olteanu, Diaz and Kazai, 2020, When Are Search Completion Suggestions Problematic?, PACM HCI 4(CSCW2)). A suggestion reads as the system's endorsement in a way a search result does not, so filtering needs its own policy, not just the result-page policy.

Popularity feeds itself. Accepted suggestions are logged as queries, which raises their frequency, which keeps them on top. This entrenches phrasings, lags behind new intents and gives manipulators a target: enough synthetic queries can plant a completion.

Offline MRR measures the wrong moment. Evaluation usually replays every prefix of the final query, but users look at suggestions only at some keystrokes. A model that wins on prefixes users never examine has won nothing.

The completion may not retrieve anything. A completion drawn from last year's logs or generated by a model can point at products, pages or events no longer in the index. Checking suggestions against the index costs latency and prevents a class of dead-end sessions.