Chapter Deepread · ML System Design Interview · Chapter 8

Ad Click Prediction: you think it's ranking, but it's quoting a price

Machine Learning System Design Interview · Ch 8 · Ali Aminian & Alex Xu · 2023

What is this chapter about?

As you scroll a social app, every dozen or so posts an ad slides in. This chapter is about how that one ad got picked — why that ad, and why for you.

A strange thing first

You probably assume the system is picking "the one you're most likely to find interesting." Order does matter, but there's a layer here that other recommendation settings don't have: money is divided by this judgment. Advertisers pay per click, and the platform has to do arithmetic between "who bid more" and "who will actually get clicked." So the system can't just say "this one is more likely than that one" — it has to name an accurate number.

Weather forecasts are the useful comparison. If all you want to know is whether tomorrow is rainier than the day after, ordering is enough. But if somebody charges insurance premiums by the chance of rain, then "70%" had better mean it really rains seven times out of ten. Ads are the second kind.

Why the old world struggled

Almost everything the system knows arrives as labels: which city you're in, what phone you use, who placed this ad, what hour you're scrolling. Any one of them is weak on its own — "lives in Shanghai" predicts nothing.

The forceful clues are combinations: somebody who bought bananas and a cookbook is more likely to want a blender. But a system that scores each clue separately and adds them up can never see a signal that only exists when two things are true at once. And there are absurdly many combinations — a few hundred clues paired up is tens of thousands of pairs, far more than people can curate by hand.

The core mechanism: let the machine do the pairing

The trick is to give every label a business card — a short string of numbers the machine works out for itself. Bump two cards together and you get a score for "how well do these two go together." The machine runs every pair, and the data decides which combinations matter. Nobody has to name them in advance. That's the chapter's first move.

The second move is how often it studies. An ad pool isn't like a film library — new ads go live every hour and what's hot changes daily. A judge trained last week hasn't seen half of what's in front of it this week. So it doesn't sit one exam a week; it studies on the job, continuously nudging itself toward the present using the impressions and clicks that just happened.

The third move is that accurate number. The system checks itself against history: of all the ads it called 2%, did about 2% actually get clicked? If not, the whole dial gets twisted back. That step is called calibration, and without it the ordering can look fine while every invoice is wrong.

How to read this approach

What's worth remembering is where the effort goes: how the machine finds combinations, how often it studies, and whether the numbers are honest. Eighty percent of the chapter lands on those three. The model itself is not the star.

What it costs

A judge that studies on the job slowly forgets what it once knew — and a version that learns something wrong can reach everybody within hours. Fast iteration and a big blast radius are the same property seen from two sides.

Remember this one line

What separates ad click prediction from every other recommendation problem is that its output goes on to divide money. It has to get the order right, say the number honestly, and keep up with a market that changes hourly. Drop any one of the three and the system starts quietly losing money.

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

In one line

This looks like one more ranking problem, but its core is a constraint no other recommendation setting has: the number the model emits gets used for billing. Ads are paid per click and ranked by bid times predicted click-through rate, so the absolute value of the score matters as much as its relative order — which turns probability calibration from a nicety into a hard requirement. Two more constraints fall out of the same setting: features are almost all high-cardinality categorical labels, so the signal hides in feature crossing; and the ad pool drifts by the hour, so the model must do continual learning.

Glossary

Impression: one ad actually shown once. CTR (click-through rate) = clicks ÷ impressions.
Bid and eCPM: the bid is what the advertiser will pay for one click; eCPM is the expected revenue of this impression, which under per-click billing is roughly bid × pCTR. Ads are ranked by that, not by pCTR alone.
Pointwise: score one candidate at a time, independently, then sort by score.
High-cardinality categorical feature: a discrete label with an enormous number of possible values, like ad ID. One-hot encoding turns it into a vector with a single 1, which explodes in width; the hashing trick instead hashes it into a fixed number of slots, trading occasional collisions for a memory ceiling.
Embedding: compress an ID into a short trainable vector, so similar IDs land near each other.
Feature cross: combine two or more features into one new signal, capturing relationships that only hold jointly.
FM / DCN / DeepFM: three families that learn crosses automatically. FM learns second-order crosses as dot products of embeddings; DCN adds a dedicated cross network for explicit, bounded-degree crosses; DeepFM runs FM and a deep network in parallel over a shared embedding table.
Log loss (cross-entropy) and AUC: the first penalises both bad ordering and dishonest magnitudes; the second looks only at ordering — multiply every prediction by 0.5 and AUC doesn't move.
Calibration: of the batch the model called 2%, the real rate should also be near 2%.
Continual learning: instead of retraining from scratch, keep fine-tuning the existing model on fresh data. Catastrophic forgetting is the side effect — it learns the new and loses the old.
Negative sampling: negatives vastly outnumber positives, so only a fraction is used for training. The cost is that the class ratio has been altered by hand, which biases predicted probabilities upward.

Where it sits

This is the seventh of the ten Part II case studies. It follows Ch7 event recommendation — also pointwise scoring, but there the weight was on hand-built features and the model stopped at GBDT. Here the scale is an order of magnitude larger and the score gets billed against, so the model moves toward automatic crossing and the evaluation moves toward calibration. Ch9 (similar listings) follows, switching to embeddings learned from behaviour sequences. The real-world analogues are Meta Ads, Google Ads and TikTok Ads.

What the chapter is solving

The setup is direct: on a social platform, every refresh has to decide which ad to show, and the goal is to maximise clicks, and thus revenue. Four constraints separate this from every earlier recommendation problem.

One: the score gets billed against. Slots don't go to whoever has the highest pCTR; they go by bid × pCTR — the expected revenue of the impression. So if the model multiplies every pCTR by 1.5, the ordering doesn't move and AUC doesn't drop, but the relative standing of a high-bid, low-CTR ad against a low-bid, high-CTR one is completely scrambled.

Two: features are almost all sparse categoricals. User ID, ad ID, device model, region, hour — after one-hot the dimensionality reaches the 10⁸ range while each sample has only a few dozen non-zero positions.

Three: the useful signal is multiplicative. "In Shanghai" and "10pm" each predict nothing; "in Shanghai × 10pm × food-delivery ad" carries signal. A linear model, by definition, cannot see that interaction.

Four: the distribution drifts by the hour. New campaigns launch, old ones exhaust their budget and drop out, events spike. A model trained yesterday faces a candidate set today containing plenty it has never seen.

What happens if you don't solve it? Miscalibration → billing and budget allocation go wrong with it. No crossing → the model only memorises coarse rules like "this advertiser generally gets clicks." No continual learning → new ads never surface, and advertisers eventually leave.

The model emits a probability, the probability times the bid decides who gets shown, and the outcome flows back as the next round of training data. A loop means bias compounds — and that the model must keep updating.

The core content, worked through

1. Translating the business problem: pointwise binary classification

The chapter models this as binary classification scored one candidate at a time: given (user, ad, context), predict P(click). Labels come free — clicked is 1, impressed-without-click is 0 — and the loss is log loss.

Why not pairwise or listwise methods, which are more natively about ranking? Because they optimise relative order and their outputs are not probabilities, and a probability that can be multiplied into bid × pCTR is exactly what ads need. The previous chapter also chose pointwise, but there it was convenience; here there is no alternative.

2. Features: three sources, one shared headache

The book splits features into three groups. Ad side: ad ID, advertiser and campaign ID, category, creative content, historical impressions and clicks. User side: demographics, context (device, time, location) and historical engagement. User × ad: interaction statistics, such as this user's historical CTR in this category. The shared headache is cardinality — there may be hundreds of millions of ad IDs, and plain one-hot is a disaster.

3. Feature crossing: why a linear model isn't enough

A model that assigns one weight per feature and sums them up — logistic regression is exactly that — cannot learn "bought bananas and bought a cookbook." It can only say "bananas add 0.1, cookbook adds 0.2." To make it visible you have to hand-build a third feature from the two: n features give n(n-1)/2 pairs, and which ones help can only be found by trying.

Sparsity makes it worse: "Shanghai × Wednesday 11pm × this advertiser" may appear three times in the training set, so the hand-crossed dimension learns essentially nothing. This is precisely what FM fixes: rather than one weight per combination, it learns an embedding vector per feature and sets the cross weight to their dot product. Even if those two never co-occurred, each vector was trained elsewhere, so the dot product still means something — parameter sharing dissolves the sparsity.

4. The model ladder: from logistic regression to DCN / DeepFM

The chapter lays the models out historically, each rung patching the one below:

Logistic regression (LR) — linear, interpretable, trivially updated incrementally. Hole: no crossing without human labour.
GBDT — learns interactions automatically (each root-to-leaf path is a cross). Hole: bad at high-cardinality sparse features, and hard to update incrementally.
GBDT + LR hybrid — trees map raw features into "which leaves did this land in," which feeds an LR that can be updated online. Trees find crosses, LR keeps up with the data. The industry default around 2014.
FM / FFM — as above, all second-order crosses learned automatically and learnable under sparsity. Hole: second order only.
DCN (Deep & Cross Network) — two parallel paths: a cross network where each layer raises the degree by one (L layers reach degree L+1), explicit and parameter-cheap; and a deep network for implicit interactions of arbitrary shape.
DeepFM — same two paths, with FM on the crossing side, and both paths sharing one embedding table.

The book lands on the DCN / DeepFM tier. The cost is that training and serving both get more expensive, and embedding tables can outgrow a single machine's memory.

Sparse IDs pass through the embedding layer into dense vectors and join the numeric features in one input. The cross network handles bounded-degree explicit crosses, the deep network handles interactions of unclear shape, and the two merge into a probability.

5. Continual learning: why it's mandatory, and where it bites

Ad data doesn't drift slowly; it turns over daily. So training isn't "a run every week" but continuous fine-tuning of the existing model on the most recent logs, usually on an hourly cadence.

Three things must come with it. (1) An online evaluation gate: every new version runs on a small slice of traffic first and isn't promoted unless metrics hold, because automated high-frequency updates also roll bad models out automatically. (2) Forgetting control: feeding only the last hour makes the model lose long-run regularities, so the usual practice is to mix fresh data with a sample of history. (3) Feature parity: training and serving must use the same feature computation, or you get training-serving skew — a class of bug invisible offline.

6. Probability calibration: the real watershed of this chapter

The definition is humble: of the impressions the model called 2%, the real click rate should be near 2%. It's a property independent of ranking — multiply every prediction by 0.5 and the order is untouched, AUC is untouched, and calibration is destroyed.

Ads contain an action that almost guarantees miscalibration: negative sampling. CTR sits in the low single-digit percent range, negatives dominate, and training usually subsamples them at some rate w — which lifts outputs systematically and has to be converted back using w. So the book treats calibration as its own stage in the serving path: raw score → calibration layer → only then a pCTR you can multiply by bid.

The evaluation consequence: AUC is not enough. It is blind to any monotone transform, so a badly calibrated model can still post a handsome AUC. Report log loss, and the blunter "predicted total clicks ÷ actual total clicks" against 1.

Key trade-offs

Table 1 · Picking a CTR model — the last column is what an interviewer wants to hear

Option	Crosses it learns	Sparse high-cardinality	Incremental update	When to pick it
Logistic regression	only what you hand it	OK with hashing	very easy	a first version, or when interpretability matters; also the last stage of a hybrid
GBDT	automatic, depth = degree	weak on ID features	hard	mostly dense numeric features, moderate data, need a strong baseline fast
GBDT + LR	trees find, LR finishes	medium	the LR stage can	you need both auto-crossing and online updates but have no deep-learning stack
FM / FFM	all second order, under sparsity	strong	yes	extremely sparse features, combinations that never co-occurred, cheap training
DCN	explicit to degree `L+1` + implicit	strong	yes	the book's choice: large scale, with GPU and embedding-table infrastructure
DeepFM	FM second order + MLP, shared embeddings	strong	yes	same; less manual feature work than DCN, slightly weaker high-order explicit crossing

Table 2 · Training cadence: freshness, cost and blast radius

Cadence	Freshness	Cost	Risk	Fits
Daily full retrain	poor: new ads wait a day	high but predictable	low, time to validate	slow-moving ad pools, smaller platforms
Hourly fine-tune	good	moderate	medium: needs an automated gate	the book's choice, mainstream social ad platforms
Near-real-time online	best: minutes	low, each sample seen once	high: one dirty window skews production at once	anti-abuse and traffic spikes, where seconds matter

The other trade-off that gets asked about is how to fit high-cardinality IDs: embeddings are the most expressive but can't learn the long tail and strain memory; hashing pins memory to a constant at the cost of collisions merging unrelated IDs; frequency cutoffs are cheapest but amount to giving up on the tail. In practice all three are stacked: embeddings for the head, hashing for the middle, an OOV bucket for the tail.

Why it matters / in real systems

The shape reaches far past advertising: any setting that predicts a probability whose value is then used as a number downstream is this chapter — a default probability feeding a credit pricing formula, a claim probability feeding an insurance premium, an on-time probability feeding a delivery promise. Conversely, pure content recommendation only needs the order to be right, and calibration is simply not an issue.

Three questions come up constantly in interviews: why CTR prediction must be calibrated while ordinary recommendation needn't be (answer with the multiplication into bid × pCTR, not a definition), how to convert probabilities back after negative sampling, and how continual learning avoids rolling a bad model out automatically. The test itself is one line: does the downstream only compare this score, or does it do arithmetic with it?

Industry evidence · claims these teams made publicly, not the book's

Google · the official DCN tutorial in TensorFlow Recommenders puts "why you need automatic crossing" more plainly than the book does: "If one has purchased both bananas and cooking books, then this customer will more likely click on the recommended blender"; the difficulty is that "In Web-scale applications, data are mostly categorical, leading to large and sparse feature space," where finding effective crosses "often requires manual feature engineering or exhaustive search"; and traditional feed-forward MLPs "cannot efficiently approximate even 2nd or 3rd-order feature crosses" — whereas DCN "was designed to learn explicit and bounded-degree cross features more effectively." tensorflow/recommenders · docs/examples/dcn.ipynb ↗
Meta · DLRM is this chapter's model shape as a shipped artefact: the input "consists of dense and sparse features. The former is a vector of floating point values. The latter is a list of sparse indices into embedding tables," and the architecture diagram labels the output directly as "probability of a click." The scale is in the repo too: benchmarks run against Criteo's Terabyte click logs, with pretrained configurations reaching --max-ind-range=40000000. facebookresearch/dlrm · README ↗
Microsoft · Vowpal Wabbit wrote both of this chapter's engineering constraints into its own README: "the memory footprint of the program is bounded independent of data," and "the size of the set of features is bounded independent of the amount of training data using the hashing trick." Crossing is built in as well — "Subsets of features can be internally paired so that the algorithm is linear in the cross-product of the subsets" — while explicitly expanding features before feeding them in "can be both computation and space intensive." VowpalWabbit/vowpal_wabbit · README ↗

A reliability diagram: predicted probability on the x-axis, the batch's true click rate on the y-axis. The violet line sits below the diagonal — the order is fine, but every number runs high, so allocating budget by bid × pCTR keeps betting on the wrong ads.

Pitfalls and debates

Reporting AUC alone. It is immune to any monotone transform — multiply all predictions by 0.5 and it doesn't budge while billing is already wrong. Report log loss and predicted-over-actual total clicks alongside it.
Forgetting to correct after negative sampling. The classic production incident: offline metrics look great, and online budget burn mysteriously doubles.
Feature leakage. Using "this ad's final CTR for the day" as a feature, which does not exist at scoring time. The subtle version is user behaviour generated after the impression.
Delayed feedback. Clicks, and conversions especially, may arrive minutes or days after the impression. Too tight a training window mislabels "hasn't clicked yet" as "won't click."
Position bias and closed-loop bias. The top slot gets clicks for free; worse, the model only learns from ads it chose to show, so anything unshown never gets a label. Exploration traffic is what breaks that.
Learning an embedding for every ad ID. Long-tail IDs appear a handful of times in their whole life. What is learnable is the advertiser, category and creative-type level, which is reusable across ads.
Treating continual learning as free. The costs are catastrophic forgetting and the blast radius of "a bad model rolls out to everyone automatically" — high-frequency updates require automatic rollback.
Overstating the gain from deep models. In public comparisons, DCN / DeepFM beat a well-tuned GBDT or FM by AUC deltas in the third decimal. That is worth real money at ad volume; a small platform copying it will lose on the trade.
Period limits. Written in 2023, the chapter stops at the DCN / DeepFM generation; behaviour sequence modelling and much larger embedding tables have become the mainline since. But "the score gets billed against, therefore it must be calibrated" does not change with the model.

Takeaways

① This chapter's output goes on to divide money: ads are ranked and billed by bid × pCTR, so the absolute value of the score matters as much as its order. That is the watershed against every other recommendation problem.

② The model is pointwise binary classification predicting P(click), trained with log loss. Pairwise and listwise are out because their outputs aren't probabilities.

③ Three feature families: ad side, user side, user × ad interactions. The shared headache is cardinality, handled by stacking embeddings, hashing and frequency cutoffs.

④ The useful signal is multiplicative: single features are weak, combinations are strong. Manual crossing explodes combinatorially and learns nothing from rare pairs.

⑤ The ladder runs LR → GBDT → GBDT+LR → FM → DCN / DeepFM. FM's key contribution is sharing parameters through embedding dot products, so combinations that never co-occurred are still learnable.

⑥ Continual learning is mandatory because the ad pool turns over hourly. It comes with three companions: an online evaluation gate, mixed sampling against forgetting, and feature parity between training and serving.

⑦ Calibration is independent of ranking. Negative sampling lifts predictions systematically and must be converted back by the sampling rate, then finished with Platt scaling or isotonic regression. Reporting AUC alone is this chapter's biggest trap.

⑧ To decide whether a setting needs calibration, ask one question: does the downstream only compare this score, or does it do arithmetic with it?