Autocomplete shows up in many products, from general web search to e-commerce search bars to code editors. Each has different scale, quality, and personalization needs, so the first job is to pin down the scope.

Clarifying Questions

Requirements

Functional Requirements:

Non-Functional Requirements:

ML Problem Framing

This is a learning-to-rank problem over a prefix-matched candidate pool. No single model can score 500 million completions per keystroke at 100,000 QPS under 50ms, so the work is split into stages. Each stage narrows the candidate pool and spends its budget on what it can actually do in the time it has.

The recall objective at the top of the funnel and the precision objective at the bottom need different model shapes. Candidate generation leans on a hand-engineered prefix data structure plus raw popularity counts. Ranking leans on a learned model that can weigh dozens of signals per candidate. Trying to collapse both stages into one model is the most common design mistake: it either takes too long or it drops too many good candidates.

Metrics

Offline Metrics:

Online Metrics:

The full system splits into an offline pipeline that builds indexes and trains models, and an online pipeline that serves suggestions on every keystroke.

On the offline side, raw query and click logs land in a data lake. An aggregator rolls them into per-query statistics (popularity, CTR, success rate) over multiple time windows. Those aggregates feed two consumers: an index builder that produces the shardable prefix index, and a training pipeline that produces the ranker artifact. Both artifacts are versioned and pushed to the online stack.

On the online side, every keystroke hits a gateway. The gateway fans out in parallel to a prefix service (which performs candidate generation against the sharded index) and to a feature store (which fetches user and session features). The ranker service scores the returned candidates using the fetched features, post-processing enforces diversity and safety, and the response goes back to the client.

Scale Numbers

Before picking a concrete design, the numbers have to line up with the budgets.

Two implications fall out. First, the prefix index is big but not huge at the scale of web infra. A two-digit number of shards, each 5 to 10 GB, fits on commodity hosts with room for replicas. Second, the ranker is small enough to load in-process alongside the prefix service if cross-service RPCs become the bottleneck, which is a common late-stage optimization.

Data Flow

The data flow has three loops running at different frequencies, which is where most of the complexity lives.

The fast loop runs every minute. A streaming aggregator in Flink or Spark Structured Streaming consumes Kafka logs and updates a small delta index of trending queries and per-query trend velocities. The medium loop runs hourly and refreshes popularity counters on the base index without a full rebuild. The slow loop runs daily and does the heavy work: full base index rebuild, ranker retraining on 30 days of data, artifact promotion through canary and into production.

Note the feedback arrow from serving back to logs. Every suggestion shown is logged alongside what the user did next. This closes the loop, but it also introduces exposure bias that has to be corrected for during training. More on that later.

Data Sources

The system pulls from four data sources, each with a distinct signal.

Query Representation and Normalization

Before anything gets indexed, queries go through a normalization pipeline. Skipping this step creates brutal long-tail issues where "NYC pizza", "nyc pizza", and "nyc pizza " live as three different queries.

The normalization pipeline does the following in order:

The same normalizer runs at index-build time and at query time, which guarantees the prefix string hashes match.

For fuzzy matching the system also stores a secondary representation: character n-grams (typically 2-grams and 3-grams) that support edit-distance lookups. This doubles some storage but is how typo tolerance becomes fast enough to hit the latency budget.

Feature Engineering

Features for the ranker split into four groups: query features (properties of the candidate completion itself), temporal features (how the candidate's popularity is evolving), context features (about the user and session), and cross features (how well the candidate matches the context).

Two things worth calling out. The popularity features exist at multiple time horizons (1h, 7d, 30d) on purpose. The ranker needs both the stable signal (30d) and the recency signal (1h), and letting it learn how to combine them is far more robust than picking one manually. And several features (prefix_match_length, user_recent_queries) are computed per request. That work has to fit in the latency budget, so they are kept deliberately cheap: integer arithmetic, not embeddings.

Baseline Approach

The simplest system that works: a trie of the top 500 million queries, each node weighted by raw popularity. On prefix "mach" the trie descends to the "mach" node, gathers all descendants, picks the top 10 by popularity, and returns them. No ranker, no personalization, no features beyond popularity.

The baseline is surprisingly strong because query popularity follows a power law: the top 10% of queries cover more than 90% of volume. If "machine learning" is the most popular "mach" completion by an order of magnitude, a naive popularity sort will land on it regardless of what the user wants. For head prefixes this gets the system to roughly 70% of the quality ceiling.

The baseline breaks in four places that matter. There is no personalization, so a user in Tokyo and a user in Mumbai get identical "mach" suggestions. There is no freshness, so a query that went viral yesterday is invisible until tomorrow's rebuild.

There is no typo tolerance, so "machne" falls off a cliff. And there is no signal about intent beyond raw popularity, so the ranker cannot learn that short queries perform better on mobile, or that session context radically changes what the user is about to type.

Advanced Approach

The production architecture keeps the prefix index as the candidate generator and adds a learned ranker plus a few targeted enhancements.

The prefix service uses a sharded radix trie, with shards keyed by a hash of the first two characters of the prefix. Each shard lives in memory on a dedicated host, replicated for availability, and rebuilt daily from aggregated logs. On a lookup, the shard router picks the correct shard, the radix trie descends to the prefix node, and returns the top 1,000 candidates by a static popularity score. That static score is not the final ranking, just a recall-preserving prefilter.

The ranker is a gradient-boosted decision tree model (LightGBM) with LambdaRank loss. GBDTs earn their place here for three reasons. They handle the mix of numerical popularity features, categorical features like device type, and sparse session features without much preprocessing. They score 1,000 candidates in around 15ms on CPU, which fits the budget. And they are easy to iterate on: adding a new feature is a pipeline change, not a model redesign.

Neural alternatives exist. Small transformer models can generate completions directly from character inputs, bypassing the prefix index entirely, and are an active area of research in production search teams.

In practice they currently supplement the main path rather than replace it because generative models are slower, have weaker coverage on long-tail queries that rarely appear in training, and produce hallucinated completions the ranker cannot easily rescue. The typical pattern is to run them as a side branch whose outputs are merged into the candidate pool, not as the core retrieval engine.

Training

Training data is built from three weeks of logged suggestion impressions and clicks. For every impression, the system records the prefix, the full list of suggestions shown, the position of each, the user and session features as they were at serve time, and the click outcome.

Labels come from the click pattern within each impression. A clicked suggestion is a positive. An unclicked suggestion that appeared above the clicked one is a negative with high confidence (the user saw it and passed). Unclicked suggestions below the clicked one are low-confidence negatives because the user may never have looked at them. Suggestions that were not shown at all are unknowns and get excluded, which is the exposure-bias problem that the evaluation section revisits.

The loss is LambdaRank, which is pairwise: for each prefix group, the model learns to score the clicked suggestion higher than each unclicked suggestion. LambdaRank weights pair gradients by the change in NDCG that would result from swapping the pair, which focuses learning on the top of the ranking where users actually look.

Three things in this snippet are worth pausing on. The group_id tells LambdaRank which rows belong to the same impression and therefore form a ranking problem; without it the model would treat every row as independent and collapse to pointwise regression.

The weight column downweights low-confidence negatives so the model does not over-penalize suggestions the user never actually looked at. And the pipeline retrains from scratch daily rather than incrementally, which trades a few hours of compute for a far simpler operational story.

Two parallel training loops run at faster cadences. Popularity counters update hourly from the batch aggregator, which keeps the candidate-generation ordering fresh without a full index rebuild. Trend-velocity counters update every 60 seconds from the streaming aggregator, feeding directly into the post-processing trending boost.

Inference Pipeline

Every keystroke that survives client-side debouncing turns into one request that traces the pipeline below.

The client debounces keystrokes by roughly 80ms to avoid a request per character, then fires to the gateway. The gateway issues two parallel RPCs: one to the prefix service for candidate generation, one to the feature store for user and session features. When both return, the ranker scores the candidates. Post-processing deduplicates, filters, and applies the trending boost. A short-TTL response cache absorbs repeat prefixes inside the same user's session.

Batch versus Real-Time

Almost every piece of data in the system is precomputed. The ranker is built once a day, the base index once a day, popularity counters every hour, trend counters every minute. What happens at request time is cheap: pointer chasing in a trie, a dozen key lookups in Redis, a GBDT scoring pass, and a few CPU instructions for post-processing.

The split matters because shifting any of these to real-time blows the latency budget. Computing popularity on the fly from the raw log stream would add 50ms and terabytes of work per query. Retraining the ranker per request is absurd. The only things done on the hot path are the things that genuinely depend on the current prefix and the current user.

Latency Budget

The budget below targets an end-to-end p99 of 100ms with roughly 45ms spent server-side. The numbers are realistic for a production autocomplete service on commodity hardware.

Two design decisions fall out of this table. Feature fetch overlaps with prefix lookup, which is why those two budgets are not additive. If they ran serially the budget would already be blown. And ranker inference gets by far the biggest slice, because scoring 1,000 candidates is real work and the GBDT has to fit that slice exactly. Halving the candidate pool to 500 would buy latency at the cost of recall, which is a real tradeoff the team might make during a load spike.

6.1 Prefix Index Structures: Trie, FST, and N-gram Hash

The prefix index is the single most performance-sensitive piece of the system, and three families of data structures compete for the job.

A radix trie (compressed trie) stores each query as a path from root to leaf, with edges labeled by character substrings. Lookup time is proportional to prefix length, typically microseconds, and updates are straightforward. Memory footprint is moderate because common prefixes are shared, but the pointer overhead per node adds up at the scale of hundreds of millions of queries.

A finite state transducer (FST), typically built as a minimal DAFSA with value annotations, is a more compact representation where common suffixes are also shared. Lucene's suggester library uses this pattern, and production teams at large search companies often land here because the compression factor over a plain trie can be 3 to 5x at this scale. The tradeoff is that FSTs are expensive to update incrementally, which is why they are usually rebuilt in full each day.

An n-gram hash index stores every substring n-gram (typically 2-grams and 3-grams) of every query in a hash map, with query ids as values. Lookups for an exact prefix are fast, but the real reason to use it is fuzzy matching: it naturally supports edit-distance retrieval by looking up the n-grams of the (possibly misspelled) prefix and taking intersections.

The diagram shows a radix trie for a tiny slice of the corpus. Edges are compressed: the "ch" edge after "mar" jumps multiple characters at once because there is no branching between them. Production tries at web scale look structurally identical, just with hundreds of millions of leaves.

In practice most systems combine at least two. A radix trie or FST handles the exact-prefix path, which is the common case, and a small n-gram index handles the fuzzy path when the exact match set is empty or too small. The radix trie is simpler to start with and scales by sharding, which is why the advanced approach in the previous section used it.

6.2 Freshness and Trending Queries

The day after a breaking news event, the base index is up to date. The hour it happens, the base index has never heard of the query. The typeahead has to surface it anyway, and it has to do it in minutes.

The solution is a dual-layer index. The base layer is the rebuilt-daily radix trie described earlier. The delta layer is a much smaller index, typically a few megabytes, that holds only queries whose short-window volume is rising meaningfully. A streaming job updates the delta layer every 60 seconds from the Kafka log stream.

At query time the prefix service looks up both layers in parallel and merges the candidate sets before the ranker sees them. The merge uses a time-decayed score of the form:

The long-term popularity term is the stable backbone. The velocity term is the first derivative of short-window popularity, and the decay factor exp(-age / tau) with tau around 6 hours means a query that spiked an hour ago gets a large boost, a query that spiked three days ago gets only the baseline. Alpha is tuned empirically.

The streaming aggregator also does a small but critical job: it filters out queries whose short-window spike looks like bot traffic or a logging glitch. A query that appears 10 million times in one minute from a handful of IPs is almost certainly not a real trend. The trending boost has to survive this filter or it will occasionally promote nonsense to the top of typeahead, which is a public embarrassment at web scale.

One subtlety is that the ranker should not learn to ignore the trending boost entirely. The simplest way to handle it is to pass velocity_1h and age_hours as explicit features to the GBDT, so the ranker learns when to trust them. The post-processing trending boost then becomes a smaller adjustment on top of an already-ranked list, not the primary freshness signal.

6.3 Spell Correction for Misspelled Prefixes

A user who types "restuarant" should still see "restaurant NYC" in their suggestions. Failing silently here is one of the most visible product flaws in autocomplete: the user feels the system is broken.

Three approaches solve this with different cost profiles.

Edit-distance over the trie (SymSpell)

Precompute every query in the index with a set of deletion variants up to edit distance 2. "restaurant" becomes "restaurant", "restaurnt" (delete 1), "restaurnat" wait, SymSpell keeps only deletions and handles insertions by comparing against the user's deletion variants at lookup. Lookup is very fast, typically under 2ms, and the approach is language-agnostic.

Noisy-channel model

Model typos probabilistically as a channel: P(typed | intended) times P(intended). The probabilities come from typo logs: common typos like "teh" for "the" get high probability. This handles context-dependent typos better than pure edit distance but needs more infrastructure.

Neural seq2seq

Train a small transformer (or a lightweight character-level LSTM) to map misspelled prefixes directly to canonical prefixes. Highest quality, especially for multi-character typos and transpositions, but the added 10 to 30ms of inference is hard to afford on every keystroke.

The practical design runs SymSpell inline as part of candidate generation. When the exact-prefix match returns fewer than some threshold of candidates (say, 20), the prefix service also issues an edit-distance lookup for the prefix and merges the results. The ranker sees a prefix_match_quality feature that indicates how much fuzziness was required, and it learns to trust high-popularity exact matches over high-popularity fuzzy matches.

The conditional dispatch keeps the fuzzy path cheap when it is not needed. For head prefixes like "mach" the exact match already returns 1,000 candidates and the fuzzy lookup is skipped entirely. For long-tail or typo-heavy prefixes the fuzzy path runs, and the ranker sorts out which matches are worth showing.

The neural seq2seq model, if the system runs one at all, sits behind a quality gate: only invoke it when the prefix is long (say, 6 or more characters), the exact match set is near-empty, and the request is not on the hottest latency path (desktop, not mobile). That keeps its cost contained while still capturing the hardest typo cases where rule-based methods fail.

6.4 Personalization Under a 50ms Budget

Full per-user ranking, where the ranker is re-run with user-specific features for every query, is straightforward to describe and impossible to afford. At 100,000 QPS, every personalized rerank consumes the whole latency budget on its own. The production pattern is to precompute global rankings and adjust them with a cheap per-user side-layer.

The architecture uses a small user tower (a two-layer MLP or a shallow transformer) that produces a 32-dimensional user embedding from recent queries, location, language, and device. The user embedding is computed lazily, cached in Redis keyed by user id with a 30-minute TTL, and fetched in the feature-store call. Most requests hit the cache.

At ranker time, the user embedding joins the per-candidate features as 32 additional numbers. The GBDT learns how to combine these with global popularity and other signals. Crucially, the ranker is trained on the same features it will see at serve time, so it learns when personalization helps and when to ignore it.

The design principle is boost, do not replace. Personalization adjusts global scores by a bounded factor, typically plus or minus 20 to 30 percent. If a global top suggestion is massively popular, the boost cannot demote it out of the top 10 based on weak personalization signals. Without this guardrail, a user who once searched for "chicago weather" could see that query promoted over "chicago" for the next month, which is a worse experience than no personalization at all.

Two failure modes matter enough to call out. The first is cold start: a brand new user has no history. The user tower is trained to output a neutral embedding for missing features, and the ranker treats cold-start candidates like any other global ranking, which is the correct behavior. The second is feedback loop: if personalization always promotes what the user clicked yesterday, the user never discovers anything new. A small exploration budget (say, 10% of impressions) samples from non-personalized top candidates to counter this, which also generates training data that is less exposure-biased toward previously-seen queries.

Offline Evaluation

Offline evaluation uses held-out session logs: take real sessions, replay them through the candidate system, and compare the produced ranking against what the user actually clicked.

The primary metric is MRR on the click, computed per impression and averaged. NDCG@10 tracks graded quality when session-success outcomes are available as relevance grades (a clicked-and-successful query scores higher than a clicked-but-abandoned one). Typed-chars-saved is a product-aligned counterfactual: for each session, how many keystrokes would have been saved if the user had accepted the highest-ranked suggestion matching their eventual query.

The evaluation set is stratified by prefix length (1-2, 3-5, 6+ characters), language, and popularity bucket (head, torso, tail). Quality degrades sharply on tail queries, so tracking them separately is the only way to notice when a model change helps head queries and silently wrecks tail queries.

One pattern that matters at scale: evaluation must be counterfactual-aware. The training data and the held-out log both come from sessions where the old ranker chose what to show. A naive evaluation rewards the new ranker for reproducing the old ranker's choices, which is not what the system should optimize for. Inverse propensity scoring weights each observed click by 1 over the probability the old system would have shown that suggestion, which removes the bias at the cost of higher variance.

Online Evaluation

Online evaluation is an A/B test with a staged rollout: 1% of traffic for 24 hours, then 10%, then 50%, then full. Primary metric is search success rate per session, because that is the product outcome. Suggestion CTR is the secondary metric. Seconds-saved is a north-star check that the product is actually helping users.

Guardrail metrics catch regressions that do not show up in primary metrics. Abandonment rate, zero-result rate on the eventual search, safety violation rate, and per-region latency p99 all have fixed thresholds, and the rollout halts if any threshold is breached.

Interleaving is a useful complement to split tests. Instead of sending user A to the treatment and user B to the control, interleaving mixes results from both rankers in the same response list for the same user. This produces tighter statistical power on preference comparisons at the cost of dev complexity, and it is how a large-scale system can meaningfully A/B test small ranker changes at low sample size.

Monitoring

Production monitoring tracks four things, each at the cadence it needs.

Health metrics (per second): request rate, error rate, latency percentiles at p50, p95, p99, and p999. Break down p99 by prefix length because mobile typeahead queries dominated by short prefixes can mask a regression on longer prefixes.

Quality metrics (per hour): suggestion CTR, suggestion-accept rate, per-position CTR distribution. The per-position distribution is a sanity check: healthy systems have a steep power-law CTR by position. If positions 3 through 10 start seeing elevated CTR, the ranker has probably lost its ordering signal.

Counter drift (per hour): audit the streaming popularity counters for volume spikes from bot traffic, logging bugs, or malformed keys. A query that appears one million times in ten minutes but has no click-through is almost certainly not a real trend.

Feedback loop and exposure bias (continuous): a small slice of traffic, typically 2 to 5 percent, serves a randomized control where the ranker's top choice is replaced by a random choice from the candidate pool. The CTR on those random slots gives an unbiased estimate of how good the candidate pool is independent of the ranker, and it also generates training data where the exposure probability is known.

The exploration slot closes the loop. Without it, the training data from any given week is entirely a product of last week's model, and the system drifts toward self-reinforcing rankings that look fine on offline metrics but slowly degrade real search quality. The 2 to 5 percent hit to CTR from random exploration is the cost of keeping the system honest, and it pays back in long-term model quality every time the team wants to ship a bigger change.