Design Search Autocomplete: The Four-Point Answer, and the Trap

📺 Prefer to watch? 90-second YouTube Short · 💬 Telegram

Originally published on software-engineer-blog.com.

"Design search autocomplete" — the suggestion dropdown under a search box — is one of the most
common system-design interview questions, and one of the easiest to answer badly. The obvious
answer is a search: the user types, you go and find the matching queries, you sort them, you
return the best ten.

That is the failure. It describes a search, and the answer is a read.

Everything below follows from one observation: the request fires on every keystroke, it has a
budget of roughly 100 milliseconds end to end, and reads outnumber writes by an enormous
margin. A design that does real work per keystroke cannot survive that ratio. So you do the work
in advance, once, for everybody.

---

1. A trie — a prefix tree

Start with the structure, because it is the thing that makes "what the user has typed so far" a
first-class object rather than a string you have to search for.

A trie stores a set of strings as a tree in which every prefix is a node on the path from the
root:

        (root)
          │
          d
          │
         da
          │
        dat
          │
       data
        /    \
  database   data structures

Two consequences worth saying out loud in the interview:

• A keystroke is one step, not one query. The client already knows which node it was on for dat; typing a moves to a child. Lookup cost is a function of the length of the prefix, not of how many queries you have indexed. Ten queries or ten billion, data is four hops.
• The prefix is a position. "What the user has typed" stops being a search key and becomes a pointer into a data structure. That reframing is the whole answer in miniature.

In production this is rarely a naïve pointer-per-character trie — it is usually compacted (a radix
tree) or compiled into a finite-state transducer so that the whole thing fits in memory and shares
suffixes. Worth naming, not worth dwelling on. The shape is what matters.

2. Precompute the top K completions at each node

Here is the trick the entire design turns on, and the point where most answers quietly go wrong.

The naïve version is: walk to the node for data, then traverse the subtree below it to
collect every completion, score them, and take the best ten. That is a graph traversal on the hot
path, executed once per keystroke — and it is slowest exactly where the traffic is heaviest,
because short popular prefixes (d, da) have enormous subtrees.

Instead, at build time, you store the finished list on the node itself:

node "data"   →   top 10, precomputed
                    data structures
                    database
                    data science
                    ...

Now the query path is:

1. walk d → da → dat → data
2. read the list stored there
3. return it

No traversal, no sort, no scoring, no ranking work of any kind. You land on the node and read
the answer that is already sitting there. That is a lookup, not a search — and it is the sentence
you want the interviewer to hear.

The cost you are trading against is space: every node carries a small list, so the index gets
bigger. That is a good trade, and it is worth volunteering. You are buying a bounded, predictable
read for a one-off increase in the size of an artifact you rebuild offline anyway.

3. Cache the hot prefixes at the edge

Short section, deliberately.

Prefix traffic is wildly skewed. A small number of prefixes — the first one or two characters of
whatever the world is currently searching for — account for most of the requests, while the long
tail is enormous and almost never hit:

 ▉
 ▉  ▊
 ▉  ▊  ▍
 ▉  ▊  ▍  ▁  ▁
 └── prefixes, by traffic ──►

So put the answers for the hot prefixes in a cache close to the user. A few thousand entries
absorb the bulk of the load and never reach your service at all. The response for a given prefix
is a small, stable blob, which is exactly the shape a cache likes. (I have written separately
about what a CDN actually is and how it differs from an application cache; here that is the only
property that matters.)

4. Rank from real query logs, rebuilt offline in batch

This is the point most answers miss, and the one that most clearly separates "I read a blog post"
from "I have thought about this".

The ranking is not alphabetical. Nobody wants the alphabetically-first completion; they want
the one people actually search for. So the score on each completion comes from real query
logs — how often that full query was issued, and often whether the suggestion was clicked when
it was shown.

And the ranking is not live. The pipeline is a batch job:

yesterday's query logs
        │
        ▼
  batch job: count + rank
        │
        ▼
  a fresh trie, shipped

Aggregate yesterday's query frequencies, recompute the top-K list for every node, build a whole
new trie, and ship it as an immutable artifact that the serving tier loads and swaps in.

The consequence is the important part: the serving path only reads. It never writes a query
back into the index it is currently serving from. The moment it does, you have put a write on the
hot path — locks, invalidation, tail latency — and given away the property you designed the whole
system to have.

Two follow-ups worth having ready, because a good interviewer will ask:

• "What about a query that trends right now?" You run a second, much smaller, fast path — a near-real-time layer over the last few minutes of logs — and merge its handful of results with the batch answer at read time. It is a deliberate exception to the batch rule, and it is small precisely because the exception is expensive.
• "How do you personalise it?" Same shape: the batch trie is the global answer, and a small per-user signal re-orders the top few. You do not build a trie per user.

The two designs, side by side

The difference is not an optimisation. It is a different system with a different failure mode:

	Search at query time (the wrong answer)	Read a precomputed answer (the right one)
What a keystroke does	Matches the prefix, collects candidates, scores and sorts them	Walks a few nodes and reads a stored list
Work per request	Grows with the size of the subtree under the prefix	Proportional to the length of the prefix — bounded, and tiny
Worst case	Short, popular prefixes: biggest subtree, highest traffic, same request	Short prefixes are the cheapest and the most cacheable
Where the ranking happens	On the hot path, per request, per user	Once, offline, in a batch job over query logs
What the serving tier does	Reads and writes the live index	Reads only; new data arrives as a swapped-in artifact
Cost you pay	CPU and tail latency, on every keystroke, forever	Storage, plus staleness measured in hours
Fails by	Falling over exactly when it is popular	Being slightly out of date

The right-hand column trades a property nobody notices (a few hours of staleness in a suggestion
list) for a property everybody notices (a dropdown that appears instantly). That is the trade the
interviewer is checking you can make.

The same trick, in LLM serving

If you work on model serving rather than search, you have met this design already — it is wearing
different vocabulary.

The prefix is still a position. When you send a prompt to an LLM, the expensive part of the
first token is processing the prompt itself. But most production traffic shares prefixes: the same
system prompt, the same few-shot examples, the same conversation replayed one turn longer. So
serving engines keep the computed attention state (the KV cache) keyed by token prefix, and a
request that shares a prefix with something already computed starts from where that left off
instead of from scratch. SGLang's RadixAttention does this with a literal radix tree over token
prefixes — the same structure as section 1, holding cached computation instead of cached
completions. "Prompt caching" in the commercial APIs is the same idea behind a billing line.

And the ranking is still offline. In a RAG system, nothing about the corpus is understood at
request time. The chunking, the embeddings, the index — all built in a batch job, ahead of time,
and shipped. The request embeds one short query and does a lookup. If your retrieval path is
embedding documents while the user waits, you have made the autocomplete mistake in a new costume.

The mapping is close enough to be worth carrying between the two domains:

Autocomplete	LLM serving
Trie node per prefix	Radix-tree node per token prefix (RadixAttention, prompt caching)
Top-K list precomputed on the node	KV cache: the attention state for that prefix, already computed
Hot prefixes cached at the edge	Hot system prompts pinned in cache; a shared prefix is a cache hit
Trie rebuilt nightly from query logs	Vector index rebuilt from the corpus, offline, and swapped in
Serving path never writes	Inference never rebuilds the index it is retrieving from

Same sentence in both worlds: do the expensive thing once, in advance, and make the request a
read.

The trap: it is a read, not a search

Here is the closing line, and it belongs at the start of your answer, not the end.

If you are running a search when the user types, you have already lost. Autocomplete answers
from something that was built hours ago. The trie was built offline. The top-K lists were computed
offline. The ranking came from yesterday's logs. All the request does on the hot path is walk a
few nodes and read a list.

Say the word precomputed in the first minute, and every other decision — why the top-K lives
on the node, why the ranking is a batch job, why the serving tier never writes — follows from it
without you having to argue for any of them separately.

The verdict

The whole answer in four lines:

• a trie → one node per prefix; a keystroke is one step down, not one query
• top K → precomputed and stored on the node, so the read is a lookup and not a traversal
• the edge → a few thousand hot prefixes absorb most of the traffic
• the logs → yesterday's real queries decide the ranking, rebuilt offline; serving never writes

And the one sentence underneath all four: the request does not compute the answer, it fetches
one that already exists. Every autocomplete design that is fast is fast for that reason, and every
one that is slow is slow because something on the hot path is still thinking.

References and further reading

The structure (§1)

• Edward Fredkin, Trie Memory (Communications of the ACM 3(9), pp. 490–499, 1960) — the original paper introducing the trie, and the source of the property §1 rests on: the key is the path, so every prefix is a node and a lookup costs the length of the key. Covers the data structure only, nothing about ranking or serving.
• Robert Sedgewick & Kevin Wayne, Algorithms, 4th ed. (Addison-Wesley, 2011) — §5.2 on R-way tries and ternary search tries, including keysWithPrefix. This is the textbook version of the "collect the completions by traversing the subtree" operation that §2 deliberately replaces.

Precomputing the completions (§2)

• Elastic, Elasticsearch Reference — Suggesters (completion suggester) — a production system with exactly this shape: a dedicated in-memory FST built at index time, optimised for prefix lookups, rather than a query against the inverted index at request time.

Ranking from query logs (§4)

• Ziv Bar-Yossef & Naama Kraus, Context-Sensitive Query Auto-Completion (WWW '11, pp. 107–116, 2011) — defines and evaluates MostPopularCompletion, ranking completions by their frequency in a query log rather than alphabetically. The direct support for §4's claim about where the ranking comes from; it does not address the batch/serving split.
• Fei Cai & Maarten de Rijke, A Survey of Query Auto Completion in Information Retrieval (Foundations and Trends in Information Retrieval 10(4), pp. 273–363, 2016) — the broad survey: candidate generation, ranking signals (popularity, time-sensitivity, personalisation), and evaluation. The best single source if you want to go past the four points, and the place to read up on the trending-query follow-up.

The LLM-serving parallel

• Lianmin Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs (2024) — RadixAttention keeps the KV cache in a radix tree keyed on token prefixes so that requests sharing a prefix reuse the computation. The same structure as §1, holding cached work instead of cached completions.

If a reference you would expect to see here is missing, say so in the comments and I will add it.

---

▶ Watch the reel: Design search autocomplete — the four-point answer, and the trap