Book Deep Read · Generative AI System Design Interview · Ch 2

Gmail Smart Compose: the latency budget moves first, quality fights over what is left

Generative AI System Design Interview · Ch 2 · Ali Aminian, Hao Sheng & Alex Xu · 2024

What is this chapter about?

You are typing an email in Gmail. Halfway through a sentence, a line of pale grey text appears after your cursor, finishing exactly the thought you were having. Press Tab and it becomes your own words. This chapter is about how that guess-as-you-type system gets built.

An analogy

Picture an assistant standing behind you. You type a word, they lean in and offer you half a sentence. To be useful they have to do three things at once: guess right, hand it over fast, and know when to keep quiet. The hard one is not the first. It is the second. The gap between your finger going down and coming back up is a fraction of a second. If the assistant needs a moment to think, you have already typed it yourself, and however elegant their phrase, it is wasted breath.

Why the old world struggled

Old-style word prediction only looked at the single word you were mid-way through, matched it against a dictionary, and stopped there. It had no idea what you were writing about. So it could finish "tomor—" into "tomorrow", but it could never produce "tomorrow at ten, does that work for you?" To continue like a human it first has to take in the whole thread: what the subject line says, what the previous email asked, where your half-finished sentence has got to. But taking things in costs time, and time is exactly what this system does not have.

How it pulls that off

Three moves.

One: read the background once and keep it. The subject line and the previous email do not change a single character while you type, so there is no point re-reading them on every keystroke. Read them once, park what you understood, and from then on only process the handful of characters you just added. That alone removes most of the work.

Two: stay small. At equal cleverness, a big model is slow and a small one is fast; when fast is the whole point, you take the slightly dumber one that arrives in time. This is the precise opposite of the usual "bigger is better" instinct.

Three: offer only the few words you are sure of — and stay quiet otherwise. It never tries to write the whole email, just three to five words, and when it is unsure it says nothing at all. Because a wrong offer costs far more than no offer: you have to stop, read it, judge it, dismiss it, and your sentence is gone. Saying nothing merely means you were not helped.

What it costs you

Because it only speaks when it is confident, it is silent most of the time. And because it has seen an enormous amount of polite boilerplate, what it hands you tends to be the most average, most template-shaped version of the sentence — useful, but it slowly sands the personality out of your email.

Remember this

In a guess-as-you-type product, the lead character is not how clever the model is. It is a timeline a few dozen milliseconds long: it decides first how big the model may be, how long it may think, how many words it may say — and only then does quality get to compete for what remains. Plus one piece of product common sense: when being wrong annoys people more than being silent, teach the system to shut up.

Want the mechanisms, the notation and the diagrams? → Switch to the deep read

In one sentence

You think Smart Compose is a question about whether a model can guess your next sentence. It is really a question about whether it can hand you that sentence before your next keystroke lands. This is the first of the book's ten case studies and the cleanest one: the latency budget moves first, pinning model size, model shape, decoding width and even the decision to speak at all — quality only gets to fight over what is left. It also demonstrates a product principle: when a wrong suggestion costs far more than no suggestion, the system must learn to stay quiet.

Glossary

Inline suggestion: grey continuation rendered right after the cursor; Tab accepts it, typing on invalidates it.
Language model (LM): predicts the next token given everything before it; put the background in front and it will continue.
seq2seq: an encoder reads the input into a vector representation, a decoder then generates word by word — the classic machine-translation shape, and two passes of computation.
Token: the smallest unit a model processes, roughly a word or half a word; generating N tokens means N forward passes.
Beam search: keeps k candidates alive and expands them together; better than taking the top scorer at every step (greedy), but compute goes up roughly by a factor of k.
Perplexity: how "surprised" a language model is by real text, lower is better; cheap to compute offline, only weakly correlated with whether users accept a suggestion.
ExactMatch@N: compares the first N words of the suggestion with the first N words the user actually wrote — all of them must match.
Acceptance rate: the share of shown suggestions the user takes with Tab — the real north-star metric online.
Coverage (trigger rate): how often the system chooses to speak. It is paired with acceptance rate: speak more often and acceptance falls.
Debounce: instead of firing on every keystroke, wait for a short pause or a word boundary before triggering.
KV cache / prefix cache: store the intermediate results of context you already processed, so the next call only computes the newly added tokens.
TPU / XLA: Google's tensor accelerator plus the compiler that turns a computation graph into native chip instructions ahead of time; the same model on that path can run an order of magnitude faster per call.

Where it sits

This is the first of the ten case studies in Part II of Generative AI System Design Interview (Aminian, Sheng & Xu, 2024). It applies the seven-step framework from Ch 1 with every step squeezed into an unusually narrow latency budget. It follows Ch 1's hard constraint that output length is simultaneously cost and latency, and leads into Ch 3 on machine translation — also sequence generation, but with hundreds of milliseconds to play with and room for a large model. Read together, the two chapters measure how far the latency variable alone can pull a design apart. In the real world it maps to Gmail Smart Compose, inline code completion and keyboard prediction: the whole family of keystroke-level real-time generation.

The problem this chapter attacks

Writing email involves a lot of repeated labour: greetings, proposing times, thanks, sign-offs — everyone rewrites these sentences. Old autocomplete looked only at the word under the cursor and matched a dictionary, blind to context, so it could finish "tomor—" but never "tomorrow at ten, does that work for you?" To continue like a human, the system has to take in the whole thread.

And that is exactly the difficulty: the background must be read, and there is no time to read it. Triggering is keystroke-level — every character typed invalidates the previous suggestion and demands a new one. Sustained typing puts keystrokes roughly 100–200 ms apart, so the entire budget for "read the background, think, produce words" is on the order of a hundred milliseconds. What happens if you ignore this? A completion system that answers in 300 ms is engineering-correct and product-nonexistent — its suggestions always land behind text the user has already typed, and turn into flickering noise. That tension drives the whole chapter.

Fig 1 · The keystroke-level timeline: the budget starts at the keystroke and ends when grey text hits the screen, and the next keystroke voids everything the pipeline just produced.

The core material, properly

1. Turn the product requirement into a language-modelling problem

Step one is not picking a model, it is defining "help me write email" as a prediction task with inputs and outputs nailed down. The input is one context string assembled from a few sources: the subject line, the previous email in the thread, metadata such as recipient and time, and the half sentence already typed. The output is not the email — it is the next few words.

"Only a few words" is a deliberate product decision, not a capability limit: the longer the continuation, the more cost and latency grow linearly in tokens, while the odds of getting the whole span right fall away quickly. One wrong word in the middle of a fifteen-word suggestion and the user deletes the lot and starts over — net value negative. The virtue of a short suggestion is that being wrong is cheap.

2. seq2seq or a single-tower LM: latency decides

There are two ways to feed the background in. seq2seq (encoder–decoder) gives the background its own encoder and lets the decoder generate from it — two passes, each specialised, and usually the higher quality ceiling; machine translation works this way. A single-tower language model concatenates everything into one long prefix and lets the same model keep going.

On paper the first is prettier; on latency the second wins outright, and the reason is caching. Throughout the typing session the subject and the previous email do not change by a single character. A flat prefix naturally lets the already-computed part stay in the KV cache, so each keystroke only pays for the handful of new tokens; the two-tower shape makes that intermediate state much harder to reuse. An architecture that turns nine tenths of its input into "already computed" beats a better architecture that recomputes every time, by a wide margin, on this budget.

Fig 2 · Two modelling shapes: the latency budget hands the decision from "whose quality ceiling is higher" to "who can reuse what was already computed".

3. Decoding: width, length, and when to stop

Every dial in decoding converts directly into milliseconds. Beam width k: expanding k candidates together is more stable but multiplies compute by roughly k, so on this budget k stays in the very low single digits, sometimes collapsing to greedy. Maximum length is hard-capped, which also rules out runaway generations. Early stopping: end at a full stop or a natural phrase rather than padding to a target length.

One detail people miss: users routinely pause in the middle of a word. The generation must be strictly prefix-compatible with what is already on screen — the first token has to continue that partial word, or the user sees a misspelled grey suggestion. In practice this means filtering candidates against the typed prefix during decoding.

4. When to shut up: asymmetric cost sets the threshold

Here is the most portable judgement in the chapter. Showing a wrong suggestion and showing nothing do not cost the same. A wrong suggestion makes the user stop, read, judge and dismiss, and it interrupts the sentence they were assembling. Showing nothing simply means "no help this time" — the user never even notices. Since false positives are expensive and misses are cheap, the confidence threshold τ should be deliberately set high, even at an unflattering coverage number.

"High model score" and "the user will accept it" are still different things, so real systems layer a trigger decision on top of the language-model score, fusing confidence, context type (replies are easier to predict than fresh emails) and the user's own acceptance history. And note that acceptance rate alone can be gamed: crank the threshold up, emit ten suggestions a day, and acceptance sails past ninety percent while product value approaches zero.

Fig 3 · Asymmetric cost: false positives interrupt writing while misses go unnoticed, so the threshold leans conservative — and coverage, the price paid, must be reported alongside acceptance.

5. Data and privacy: nobody may look at the training set

The training corpus is real users' email, which brings a constraint no other chapter has: no engineer may inspect the data row by row. The entire pipeline has to work blind — automated language, length and quality filters, removal of templates and machine-generated mail, deduplication; aggregate statistics only for data profiling; error analysis confined to synthetic data or explicitly licensed corpora.

Harder still is memorisation risk: models memorise strings that appear often in training, and the frequent strings in email are precisely phone numbers, addresses and verification codes. So sensitive data has to be stripped on the way in, and caught again on the way out — never surface something that looks like one person's private information as a suggestion to another. Personalisation visibly raises acceptance, but it requires a per-user model or adapter, which means redoing both the privacy and the cost arithmetic.

6. Evaluation: offline and online metrics measure different things

Offline you use perplexity and ExactMatch@N (do the first N words of the suggestion match what the user actually wrote, word for word?): cheap, regression-friendly, adequate as a pre-launch gate. But they only reward text identical to the human's, and score a perfectly good paraphrase at zero — while users accept paraphrases happily.

Online is where the truth lives: acceptance rate, coverage, characters saved per acceptance, plus the p90 latency you must never stop watching. Read the four together: latency going up drags acceptance down (the suggestion arrives too late), and moving the threshold pushes acceptance and coverage in opposite directions. Any one of them alone will tell you something false.

Key trade-offs

Table 1 · Three ways to feed in the same background

	n-gram / dictionary	seq2seq encoder–decoder	single-tower LM (flat prefix)
Context visible	current word only	full background, dedicated encoder	full background, all in the prefix
Cost per keystroke	near zero	both passes recomputed	only new tokens; rest from cache
Quality	can finish a word, nothing more	highest ceiling on paper	slightly lower, gap acceptable
Cost	limited product value	hard to fit in 100ms	longer prefix, bigger bill: trim the background

Table 2 · Where the milliseconds come from

	smaller model	accelerator / compiler	cache the unchanged prefix	compress decoding
Saves	compute per forward pass	same compute, faster	turns most input into "already done"	fewer steps, fewer branches
Magnitude	several-fold	up to an order of magnitude	depends on context share; usually the big one	roughly linear in `k` and length
Price	quality drops directly	cost and portability	more memory, invalidation to handle	blander candidates, no long suggestions
Reach for it	only when nothing else fits	when traffic justifies it	always first: quality untouched	last resort for tail latency

Table 3 · Which way to move the threshold

	lower τ (speak more)	higher τ (speak less)
Coverage	high	low
Acceptance	diluted, falls	flattering — possibly bought with silence
Felt experience	grey text flickering, writing interrupted	appears rarely, right almost every time
Fits	predictable cases such as template replies	the default, especially for fresh emails

Why it matters / in real systems

What this chapter really hands you is the general solution for the whole real-time completion category: Gmail Smart Compose, Copilot's inline completion, keyboard prediction — identical skeleton. Keystroke trigger, debounce, cache the unchanging context, small model and short generation, a threshold deciding whether to speak, acceptance rate online.

It has one more use in interviews: this is one of the few questions where you can legitimately say "I am choosing the worse model". Turning "the budget is a hundred milliseconds, therefore I give up the higher-quality two-tower design" into a complete chain of reasoning is worth more than reciting any architecture name.

Industry evidence · claims made publicly by the companies and projects themselves, not by the book

Google (the Gmail Smart Compose team): their KDD 2019 paper Gmail Smart Compose: Real-Time Assisted Writing published the latency arithmetic for this exact product: the target was to keep each suggestion under 100ms so users would not perceive a delay, with a reported p90 of about 60ms. The paper also states that under comparable conditions LSTM latency per suggestion was markedly lower than Transformer, and that inference was moved onto TPUs with XLA compilation — on ordinary CPUs average serving latency was in the hundreds of milliseconds, which was unacceptable. This is the most direct primary evidence that the latency budget moves first.(Chen et al., KDD 2019; arxiv.org and dl.acm.org are blocked by this site's egress proxy, so the citation is text-only.)
Google Cloud (2026): frames the same trade-off as a curve — on a fixed hardware budget "you can trade latency for throughput. But, you can't improve one aspect without sacrificing the other, unless the frontier curve itself moves" — and notes that prefill and decode cannot both be optimal at once. Their measured result: routing changes alone, with no change of hardware or model, cut TTFT by 35% and doubled the prefix cache hit rate from 35% to 70%. Confirms that caching and routing are latency you get without paying in quality.Google Cloud Blog, "Five techniques to reach the efficient frontier of LLM inference" ↗
NVIDIA (TensorRT LLM): has hardened these same moves into product features — "algorithmic runtime optimizations (Prefill-Decode disaggregation, Wide Expert Parallelism, Speculative Decoding, etc)" alongside KV cache reuse optimizations. Cache reuse plus compressed decoding is not one product's local trick; it is standard practice across the inference stack.NVIDIA/TensorRT-LLM README ↗
A counter-example: Google switched part of the capability off. In November 2018 it was widely reported that Google had banned gendered pronouns in Smart Compose — the trigger was the system completing "I am meeting an investor next week" with a male pronoun. The team judged that this class of error could not be fixed reliably, so the whole capability was removed. In generative products the safety boundary is often "don't do it" rather than "get it right".(Reuters, November 2018, reporting a Google product manager's public explanation; reuters.com is blocked by this site's egress proxy, so the citation is text-only.)

Pitfalls and open questions

Opening with the model architecture. The right opening is to ask for the latency budget and the trigger model, not how many layers the network has — before the budget is fixed, no architectural choice has a criterion.
Reporting acceptance rate alone. It can be inflated with silence. Acceptance, coverage, characters saved and p90 latency have to be reported as a set, or the metric itself is the loophole.
Writing the SLO against the mean. The experience is decided in the tail: 50 ms mean with a 400 ms p99 means a wasted flicker every few dozen keystrokes.
Treating perplexity as an acceptance test. It correlates only weakly with acceptance: paraphrases score badly while boilerplate, being frequent, scores well — one source of completion systems' natural pull toward the template.
Forgetting prefix compatibility. Stopping mid-word is normal, and the continuation must join onto the characters already typed or the screen shows a misspelling in grey.
Underestimating how far the privacy constraint spreads. "Nobody may read the training data" propagates into cleaning, error analysis and production debugging — when a bad suggestion is reported you cannot even open the email. That, not lack of effort, is why systems like this iterate slowly.
Dated in one respect. The prototype system comes from the era of LSTMs and small Transformers; speculative decoding (a small model drafts, a large one verifies in parallel) and capable on-device models have since loosened the conclusion that only small models qualify. The direction of reasoning is unchanged: measure the budget first, then choose the shape.

Takeaways

① The first of the ten case studies, and its lesson is: the latency budget moves first; quality fights over what is left.

② Keystroke-level triggering means the previous suggestion is voided at any moment; the whole budget, round trip included, is on the order of a hundred milliseconds — an over-budget suggestion is not slow, it is waste.

③ Task definition: input = subject + previous email + metadata + the half sentence typed; output = the next three to five words — a short suggestion is cheap to get wrong.

④ seq2seq has the higher ceiling, but the single-tower LM wins because its prefix is cacheable: turning most of the input into "already computed" is worth more than architectural elegance.

⑤ Latency savings in priority order: cache first (free of quality cost) → accelerator and compiler → compressed decoding (small beam, capped length) → only then a smaller model, which costs quality directly.

⑥ False positives and misses are asymmetric: a wrong suggestion interrupts writing, silence goes unnoticed — so the threshold leans conservative and the system learns to shut up.

⑦ Prefix compatibility: users stop mid-word, and the first generated token must join on cleanly.

⑧ Offline metrics (perplexity, ExactMatch@N) only reward literal matches and score paraphrases at zero; online, the four numbers — acceptance, coverage, characters saved, p90 latency — must be read as a group.

⑨ The training data is private email: nobody may inspect it row by row, so cleaning and debugging run on automation and aggregates, and the model must be kept from memorising high-frequency phone numbers and addresses.

⑩ Sometimes the safety boundary is "don't do it" rather than "do it right" — for errors like gendered pronouns, removing the whole capability is a legitimate answer.