Autocomplete and Typeahead That People Trust

Autocomplete is the only part of a search product with a latency requirement set by human motor control rather than by a service-level objective. Miss it and the feature does not feel slow — it feels broken, because the suggestions are answering a query the user has already finished typing.

The budget is set by typing speed

A competent typist producing a search query manages somewhere around 150 to 250 milliseconds between keystrokes. Take 200 ms as the working assumption. A suggestion list that arrives after the next keystroke has landed is stale by definition: it describes a prefix that no longer exists on screen. So the entire round trip has to fit inside one inter-keystroke interval, and that budget has to be spent explicitly:

Two consequences follow immediately. First, autocomplete cannot share a service with search itself if search is allowed to take 200 ms — separate deployment, separate index, separate budget. Second, debouncing is not the optimisation people think it is. With a 100 ms debounce and a 200 ms typing interval, every keystroke still fires, because the pause always exceeds the debounce. Debounce only suppresses bursts. The change that actually helps is cancelling in-flight requests the moment a new keystroke arrives.

The index that makes it possible

The classical structure is a trie over the suggestion vocabulary, with the top-k completions precomputed and stored at every node. A lookup walks the prefix and reads the list — O(len(prefix) + k), with no scoring at query time at all, because the scoring already happened when the node was built.

That precomputation is the trick worth internalising. A typeahead system that scores candidates at request time will always be at the mercy of how many candidates a short prefix matches, and a one-letter prefix matches everything. A system that stores the answer at the node has the same cost for “a” as for “antidisestablish”. The cost moves to the rebuild, which is a batch job you run nightly.

Typo tolerance breaks the clean structure, because a misspelled prefix walks off the trie. The usual answer is a second, slower path: on a prefix that returns fewer than some threshold of suggestions, fall back to an edit-distance-tolerant lookup — an FST with fuzzy traversal, or the deletion index described in query understanding. Keep it as a fallback tier rather than the default, because it is slower and because tolerating typos on a prefix that was correct produces confusing suggestions.

Ranking suggestions

The baseline is most-popular-completion: order candidates by how often the full query was issued. It is genuinely hard to beat on head traffic and it should be the thing anything fancier is measured against. Signals worth layering on, in roughly descending order of value per unit of effort:

• Success weighting. Weight a query’s frequency by whether it led to a click or a conversion rather than by raw issuance. Popular queries that fail are exactly what you do not want to promote.
• Recency. An exponentially weighted frequency with a half-life of days lets seasonal and news-driven queries surface without a model. This is where most of the perceived “freshness” of a good typeahead comes from.
• The user’s own history, pinned above the global list and visually distinguished. This is the one form of personalisation in search that is almost always correct, because the user recognises their own past query and the signal is unambiguous — contrast with the general case in personalisation versus relevance.
• Context. The category being browsed, the previous query in the session. Bar-Yossef and Kraus (2011) formalised context-sensitive completion; the practical version is that a prefix typed inside a category should not suggest completions from another one.

One correctness bug is worth naming because nearly every hand-rolled implementation ships it. Suggestion responses arrive out of order — the request for “lap” can return after the request for “lapto” — and a naive handler renders whichever arrived last. The list then flickers back to a shorter prefix. The fix is a monotonic sequence number per request, with the client discarding any response whose sequence is lower than the highest already rendered:

let issued = 0;
let rendered = 0;

async function onKeystroke(prefix) {
  const seq = ++issued;
  const results = await fetchSuggestions(prefix);
  if (seq <= rendered) return;   // a newer response already won
  rendered = seq;
  render(results);
}

Two rules that are not optional

Suggestions built from query logs are user-generated content that you are publishing under your own brand, and they need to be treated that way.

• Never suggest a query fewer than k distinct users have issued. This is k-anonymity applied to a suggestion index, and it is the rule that stops a pasted email address, an order number, a session token or somebody’s medical query from appearing in a stranger’s dropdown. A threshold in the tens of distinct users, over a bounded window, costs you almost nothing in coverage — those queries are in the tail by construction — and it is the difference between a suggestion index and a data leak. The public history of query-log releases, of which the 2006 AOL release is the best known, is a history of people underestimating how identifying a query is.
• Never suggest a query that returns nothing. Validate every suggestion against the live index at build time and drop the ones with no results. A suggestion is a promise that a result exists behind it, and this is the cheapest promise in the product to keep.

Beyond those two, a blocklist for slurs and for defamatory entity-plus-attribute completions is standard, and it needs to be reviewed rather than generated. Suggestions are the part of a search product most likely to end up in a screenshot.