Autocomplete, suggestions & spelling at scale

The reranker in lesson 45 ran once per query. Autocomplete runs once per keystroke — it is the tightest-latency, highest-QPS surface in all of search, and it quietly authors the query distribution that every downstream stage in this track sees. The design is dominated by two things: the latency budget and the data structure.

The one engineering line to carry through: autocomplete is a latency-bounded retrieval problem on a stream of growing prefixes, where the data structure decides whether you can answer in the budget, and the ranking decides whether the answer is good. Everything below is a consequence of "you have ~100 ms, you get hit on every keystroke, and the corpus is huge."

QAC as prefix → ranked completions

Query autocomplete (QAC) is the box that, as the user types a prefix, proposes a short ranked list of full queries that begin with it. Formally: given prefix p, return the top-k completions c such that p is a prefix of c, ranked by a score s(c \mid p). The naive store — a hashmap keyed by every prefix → its completion list — is the first thing to reject in an interview, so build up to why.

Why a hashmap of prefixes blows up

A query of length L has L prefixes (i, ip, iph, …). If you key a hashmap by prefix and store the candidate list under each, every query contributes to L entries, and the completion lists overlap massively (the list under ip is nearly the list under i). For a log of Q distinct queries of average length \bar{L}, you store O(Q \cdot \bar{L}) prefix keys, each pointing at a list that can be hundreds of entries — the same completions copied under every one of their prefixes. At Q = 10^8 distinct queries, \bar{L} = 20 chars, that is 2 \times 10^9 prefix keys before you count the duplicated completion payloads. The redundancy is the whole problem, and it is exactly what a tree removes by sharing prefixes.

The trie

A trie (prefix tree) stores the query set as a tree where each edge is a character and each root-to-node path spells a prefix. Shared prefixes share nodes — ipad, iphone, ip address all share the path i → p. A node can be marked terminal (a complete query ends here) and carry a count.

The lookup cost. Walking to the node for a prefix of length L is L node hops — one per character — independent of the corpus size N. That is the headline property: descending to ip costs 2 hops whether the log has a thousand queries or a billion. Contrast with the cost of then producing ranked completions: the terminals live scattered across the entire subtree under ip, and that subtree can hold a huge number of completions. If you collect-then-sort the subtree, the cost is O(m \log k) for m terminals in the subtree — and for a head prefix like a or i, m can be in the millions. The O(L) descent is free; the subtree traversal is what kills you.

Store top-k at each node, or traverse the subtree?

This is the central QAC engineering decision, and it is a precompute-vs-query-time trade.

The production answer is usually both: materialize top-k on nodes near the root (short prefixes = giant subtrees = the dangerous ones), and traverse on demand for long, rare prefixes whose subtrees are tiny. Materialization converts an unbounded query-time scan into a bounded O(L+k) read by paying memory and an offline rebuild — exactly the cache-vs-compute pattern you will reuse for head-prefix caching below.

Compressing the trie: radix tree, FST, marisa-trie

A plain trie with one node per character is memory-hungry — pointer overhead dominates, and long non-branching chains (the reland in ireland) waste a node per char. Three compressions, in increasing sophistication:

The common thread: the dynamic, pointer-based trie is good for prototyping and for the small online layer; the serving layer at scale is an immutable, compressed structure (FST or succinct trie) rebuilt offline, because read-only buys both 5–20× memory savings and cache-friendly traversal — and the query log only changes meaningfully on the timescale of a rebuild anyway.

Ranking the completions

Descending the trie gives you the candidate set; ranking decides the order of the 5–10 you actually show. Build it up.

MPC — the Most-Popular-Completion baseline

Most-Popular-Completion ranks the completions of a prefix by how often each was issued as a full query in the log. It is the maximum-likelihood estimate of "what query does someone who typed this prefix most likely want," and it is a shockingly strong baseline because query frequency is enormously skewed (Zipf, lesson 40) — the top completion usually dwarfs the rest.

Worked MPC. Prefix ip, with this completion-count table from the log:

Top-3 shown: iphone, ipad, iphone 15. The arithmetic is trivial — that is the point. MPC needs nothing but counts, and it captures most of the value. Note iphone and iphone 15 are near-duplicates; hold that thought for diversity.

Adding recency & trending

MPC is blind to time: it ranks by all-history popularity, so a query that just started trending today is buried under stale all-time favorites, and a query that was huge last year but is now dead still ranks high. The fix is to blend a recency signal — e.g. counts over a short recent window, or an exponentially-time-decayed count. A simple blend:

Worked recency reorder. Suppose a new model just launched and the last-24h window shows a surge for iphone 15. Normalize each column to a share, then blend with \lambda = 0.5:

Recomputing cleanly: blend scores are iphone 0.410, iphone 15 0.340, ipad 0.205. So the recency blend lifts iphone 15 from rank 3 to rank 2, ahead of ipad, while the all-time leader iphone still holds rank 1. That reorder — trending content surfacing above a stale evergreen — is the entire reason production QAC is not pure MPC. (Trending detection itself is usually a separate signal: flag completions whose recent rate is anomalously high vs their historical baseline, which is how "spiking" queries get a temporary boost.)

Learned ranking, context & personalization

Beyond recency, a learned ranker (the LTR machinery from lesson 44, but on a tiny candidate set under a brutal latency budget) blends features:

• Popularity & recency — the MPC count and time-decayed count above, plus trending flags.
• Context — location (weath… → local weather; restaurant queries near the user), time-of-day, device, and crucially the session prefix: the user's prior query in this session disambiguates (after searching flights, the prefix new… should favor new york over new movies).
• Personalization — the user's own history: someone who repeatedly searches a brand should see it float up. Personal completions are a strong signal but must be privacy-scoped and never leak across users (a completion from your history must not appear for someone else).
• Quality / safety demotion — demote or remove toxic, unsafe, NSFW, defamatory, or low-quality completions (see safety section). This is a hard gate, not a soft feature, for the worst classes.

Because the candidate set is small (the few hundred terminals under the prefix, or the materialized top-k), the ranker can be richer per-candidate than the millisecond-budget suggests — but the model itself must be tiny (often a GBDT or a small linear/logistic model on cached features), since it runs on every keystroke.

Diversity among suggestions

The MPC list above showed iphone and iphone 15 adjacent — near-duplicates that waste a slot. Showing 10 variants of the same head query is bad UX; users want a few distinct intents. The fix is the same diversity/MMR idea you saw in reranking (lesson 45): penalize a candidate that is too similar (token overlap, or same linked entity/category) to one already chosen. Practically, dedupe by stem/entity and cap how many completions share a root, so the list spans iphone, ipad, ip address rather than five flavors of iPhone.

The latency & QPS reality

This is the section that makes autocomplete different from every other surface in this track.

Per-keystroke requests and the QPS multiplier

If autocomplete fires on every keystroke, a query of length 10 can generate up to ~10 requests (one per character typed). That makes autocomplete QPS a multiple of search QPS.

Debouncing & cancellation

Debouncing waits a short interval (~100–150 ms) after the last keystroke before firing a request, so a fast typist banging out iphone fires one request (after they pause) instead of six. Pair it with request cancellation: when a newer keystroke arrives, cancel the in-flight request for the older, now-stale prefix — you never want to render completions for iph after the user has already typed iphone (out-of-order responses cause flicker). Debouncing is the cheapest single lever on autocomplete load; it is a client-side change that can cut backend QPS several-fold.

Caching the Zipf head

Query (and prefix) frequency is Zipf-distributed (lesson 40): a tiny number of head prefixes account for a large fraction of traffic. That makes prefix-level caching extraordinarily effective — cache the completion list for the hottest prefixes (a, fa, face, amazon, …) at the edge / in memory, and most requests never touch the trie service.

The latency budget

The target is to repaint suggestions within roughly ~100 ms of a keystroke (faster feels instant; slower than ~200 ms feels laggy and users out-type the box). That budget covers network RTT + debounce + backend lookup + render. It leaves the backend only tens of milliseconds, which is exactly why the lookup must be O(L+k) (materialized top-k), why the head is cached, and why the ranker must be tiny. There is no room for a 100 ms LLM call on the keystroke path (contrast lesson 41's LLM-on-the-tail framing — autocomplete is even more latency-constrained than query understanding).

Coverage of unseen prefixes & cold completions

MPC/trie can only complete prefixes that exist in the log. But users type prefixes the log has never seen — a brand-new product name, a rare long-tail phrasing, a fresh news entity. If the trie node doesn't exist, you return nothing, and an empty autocomplete is a missed assist. Three coverage mechanisms:

• N-gram backoff. If the full prefix has no completions, back off to a shorter suffix of the typed words. Borrowing the language-model idea: if cheap iphone cabl… has no logged completion, back off to completing just the last token cabl… → cable using its own popularity, then re-attach the earlier context. This is the same back-off that smooths sparse n-gram LMs — when the specific context is unseen, fall back to a less specific one.
• Synthesize from document titles / catalog. The query log is not the only source of legitimate completions. Mine product titles, catalog entries, entity names, and document headings to build candidate completions for queries no one has typed yet — a new SKU's title becomes a completable suggestion the day it is listed, before any log evidence exists. These get a lower prior than log-backed completions (no demonstrated demand) but they cover the cold start.
• Handling the long tail. For rare prefixes the materialized-top-k layer doesn't bother caching; you traverse the (tiny) subtree on demand, or fall back to backoff/synthesis. The tail is where coverage techniques matter and where the latency budget is easy (small subtrees); the head is where caching matters and coverage is trivially solved by sheer log volume.

"Did you mean" / spelling at scale

Lesson 41 built the noisy-channel spelling model: the user intended a correct query c but the channel emitted the observed string w, and we pick

That lesson worked teh → the by hand (Damerau transposition gives a 1-edit channel; the query-log prior beats tea/ten by ~150×). Here we extend it with the two pieces that make it a scale problem: how candidates are generated efficiently, and how the autocorrect/suggest/fallback decision is actually made.

Candidate generation via bounded edit distance

You cannot score P(c \mid w) over the whole vocabulary — you first need a small candidate set of plausible corrections. The standard bound is edit distance ≤ 2 (Damerau-Levenshtein: insertions, deletions, substitutions, adjacent transpositions), because the overwhelming majority of real typos are within two edits, and the candidate count explodes beyond that. Two ways to enumerate within the bound efficiently: a BK-tree (metric tree that prunes by triangle inequality on edit distance) or a SymSpell deletion index (precompute deletions of dictionary words; at query time generate only deletions of w and intersect — far fewer candidates to generate than the full edit neighborhood).

Keyboard-aware channel costs

As lesson 41 noted, not all edits are equal: substituting two physically adjacent keys (s \leftrightarrow d) is a far more probable slip than distant keys (s \leftrightarrow p), so the channel cost of an adjacent substitution is lower, raising P(w \mid c) for keyboard-plausible typos. The channel model is therefore a weighted edit distance whose per-edit costs come from a confusion matrix (learned from query-reformulation logs: pairs where a user typed w then immediately retyped c are gold typo→correction labels). The prior P(c) is still the query-log LM — the domain lives there, exactly as in 41.

The autocorrect vs suggest vs no-results-fallback decision

The output is not just a ranked candidate; it is a decision with three actions, gated on the posterior margin and whether the original query has results.

The deciding numbers are the same two from 41: the posterior margin (how dominant is the top candidate) and the original's result count (does the typed form already work). The trap, repeated from 41 because it is the most common spelling-product mistake: a wrong silent autocorrect is infuriating — the user sees results for a word they did not type — so the silent-rewrite gate must be conservative (huge margin + zero original results), and everything else is a suggestion the user can ignore.

Safety & abuse — autocomplete as a liability surface

Autocomplete is uniquely dangerous because it puts words in the engine's mouth. A search ranking is a response to what a user typed; a completion is the engine proposing a query. If the engine autocompletes a person's name into a defamatory or false phrase, or a neutral prefix into a slur, hateful, self-harm, or illegal suggestion, that is the engine appearing to author it — a brand and legal/PR liability that has produced real lawsuits and regulatory action. Mechanisms:

• Blocklists & pattern filters. A curated denylist of completions and substrings (slurs, illegal-content phrasings, named-individual defamation) that are removed regardless of popularity. This is a hard gate applied after ranking, before render.
• Classifier demotion. A toxicity/safety classifier scores completions; high-risk ones are demoted or suppressed. Catches what static lists miss, at the cost of a model in the path (kept tiny / precomputed offline per completion).
• Spam / poisoning defense. Because completions come from the query log, an attacker who scripts a query millions of times can try to inject a completion (autocomplete poisoning). Defenses: per-user/per-IP rate-limiting in the log aggregation, anomaly detection on suspiciously spiking unique-source-poor queries, and minimum distinct-user thresholds before a query is eligible to be a public completion (one bot typing a phrase a million times should not create a public suggestion).
• Named-entity protection. Extra caution around real people, protected classes, and sensitive topics (medical, self-harm) — often a policy of not autocompleting beyond a person's name, or routing sensitive prefixes to vetted suggestions.

The framing: popularity is the default signal, but safety is a veto that overrides popularity. A completion can be the single most popular continuation of a prefix and still be removed — the brand cost of surfacing it dwarfs the relevance gain.

Interactive · autocomplete trie explorer

Type a prefix and see the ranked completions from a small built-in query log. Toggle the recency blend to watch trending completions reorder. The KPIs show what the lookup actually cost: trie nodes visited on the descent, candidate completions considered in the subtree, and an approximate latency. The log, counts, and latency model are a toy — the structure (O(L) descent, subtree candidate set, MPC vs recency blend) is the real lesson.

Interview prompts you should be ready for