Autocomplete with ML

01 · CONTEXT AND REQUIREMENTS

What it means to complete a query while the person types

In query autocomplete, the person starts typing and the system offers ways to finish the search. Huyen's exercise material includes, among its ML problems, completing the sentence of someone who is writing, and warns that the questions are ambiguous on purpose: it is up to the candidate to ask clarifying questions and bound the scope. A public ML project roadmap asks, right at the start, for scope, scale, and personalization, as well as latency and prediction scale as performance requirements. These agreements are the starting point of search system design.

This case splits the problem into two blocks: a prefix index, which returns candidates quickly, and a model that orders them. The split is a design choice of this article, not a requirement of the sources; the ML roadmap only mentions candidate generator and ranker as modeling modules.

02 · WHERE THE SUGGESTIONS COME FROM

Past searches, freshness, and context

According to Google, Autocomplete predictions reflect searches that have already been made, and they appear as soon as the person starts typing. The systems start by looking at common and trending queries that match what was typed, but Google states that the result is not limited to showing the most common ones. The diagram below translates this into a query path, with a prefix candidate index ahead of ranking.

1. As soon as the person starts typing, the predictions must appear in the search box; the suggestion service is what assembles them.

2. The service looks among common and trending queries for those that match what the person started typing.

3. The searcher's language and the location they search from enter the selection, because they make predictions far more relevant.

4. The ranker is not limited to the most common queries: growing interest in a topic can bring a trending prediction to the front.

5. A final filter prevents useless predictions, or ones that violate policies, from reaching the displayed list.

For long queries, Google says the systems may move from predicting the whole search to predicting parts of it.

03 · FRESHNESS AND LATENCY

Batch, fast path, and time budget

The ML roadmap distinguishes batch prediction, periodic, precomputed and stored to be retrieved when needed, with high throughput, from online prediction, made when the request arrives, with low latency. It also cites the hybrid approach, which combines the two.

1. In Google Autocomplete, predictions reflect searches that have already been made; the diagram starts from that history.

2. The batch computation is periodic and precomputed, and its result is stored in the index to be read when needed.

3. Growing interest in a topic can bring a new prediction to the front even if it is not the most common; the ML roadmap cites the hybrid approach, which combines batch and online.

4. The reciprocal rank of the first click and direct negative feedback are online metrics cited for evaluating what the system delivers.

On the time budget, the ML roadmap asks to establish the prediction latency. As a point of comparison, Google's Smart Compose uses machine learning to offer sentence-completion suggestions as the person types. Because it gives predictions on every keystroke, the response should ideally arrive within a hundred milliseconds so the person does not notice delay, and balancing model complexity and inference speed was a critical problem.

04 · SUGGESTION SAFETY

What should not appear

Google states it has systems designed to prevent useless predictions or ones that violate policies. The systems identify whether reliable content is likely to exist for a search and, if that probability is low, can automatically prevent the prediction from appearing. When removing a prediction, Google removes the specific one and often uses pattern matching and other methods to catch close variations.

05 · MEASUREMENT AND DEPLOYMENT

How to know whether the suggestions help

The ML roadmap separates offline metrics, such as Precision@k and Recall@k (which do not consider ranking quality), mAP, MRR, and nDCG, from online metrics, such as the reciprocal rank of the first click. It also lists counter metrics, such as direct negative feedback: hiding or reporting.

To put a change live, the same roadmap lists A/B experiments, shadow deployment, and canary release.