Design an ad click-through-rate prediction system

The problem

Someone opens a news app. There is one ad slot at the top of the article, and thousands of advertisers whose targeting matches this reader. Some pay per click, some pay per thousand impressions, some pay per app install. In about a hundred milliseconds the system must choose one ad and decide what that advertiser pays.

The key number is the pCTRPredicted click-through rate: the model's estimate of the probability that this user clicks this ad if it is shown in this slot now., the predicted probability that this reader clicks this ad here. An advertiser bidding 2 dollars per click is worth 2 x 0.01 = 2 cents per impression if pCTR is 1 percent, and 10 cents if pCTR is 5 percent. The auction compares ads by that expected value, and the price the winner pays is computed from it too.

Think of a market stall owner who rents the best spot at a fair to whichever seller will earn them the most. A seller who offers 10 percent of each sale is only worth more than one who pays a flat fee if they will actually sell enough. The stall owner has to estimate sales, and the estimate has to be honest in absolute terms: guessing every seller's sales twice too high would make every percentage offer look better than every flat fee. pCTR is that estimate.

Requirements

Functional

• For each ad request (user, page or app screen, slot, time), score the eligible ads with pCTR and run an auction that picks the winner and its price.
• Support several billing types: cost per click (CPC), cost per thousand impressions (CPM), and conversions, compared on one scale.
• Log every impression with its features and the model version, and join clicks to impressions for training.
• New ads and new advertisers must be servable on their first impression.

Non-functional

• Latency: the whole ad decision in about 100 ms; the pCTR model gets perhaps 10 to 20 ms for all candidates.
• Calibration: average predicted CTR must match observed CTR overall and on every important slice (country, device, ad format, new ads), within a few percent.
• Freshness: the model should reflect new ads, new campaigns and shifting behaviour within hours, not weeks.
• Scale: billions of requests a day, with features that have billions of distinct values.

Out of scope

• Candidate selection by targeting rules, budgets and pacing (it supplies the eligible ads).
• Auction design in depth (reserve prices, multi-slot pricing) and conversion attribution.
• Brand safety and ad review, which use classifiers like the one in Design a spam / content moderation classifier .

Estimates

Assumed numbers for a large ad network, not any company's figures:

# Back-of-envelope sizing for an ad click prediction system. Every input is an assumption; change them and re-run.
ad_requests_per_day = 5_000_000_000   # page views and app screens that have an ad slot
peak_factor = 2
candidates = 200                      # eligible ads per request after targeting and budget filters
heavy_scored = 50                     # survivors of a light model, scored by the main pCTR model
ctr = 0.01                            # assumed average click-through rate on shown ads
neg_rate = 0.025                      # keep 2.5 percent of non-clicks for training
hashed_ids = 2_000_000_000            # feature ids (ids and crosses) after hashing
dim, bytes_per_float = 16, 4

peak_qps = ad_requests_per_day / 86_400 * peak_factor
print(f"ad requests at peak          {peak_qps:,.0f} per second")
print(f"pCTR predictions at peak     {peak_qps * heavy_scored / 1e6:,.1f} million per second (heavy model)")
print(f"                             {peak_qps * candidates / 1e6:,.1f} million per second (light model)")
clicks = ad_requests_per_day * ctr
print(f"impressions / clicks per day {ad_requests_per_day / 1e9:.0f} billion / {clicks / 1e6:,.0f} million")
rows = clicks + (ad_requests_per_day - clicks) * neg_rate
print(f"training rows per day        {rows / 1e6:,.0f} million after negative downsampling at {neg_rate}")
print(f"share of positives in rows   {clicks / rows:.1%} (was {ctr:.1%})")
table_gb = hashed_ids * dim * bytes_per_float / 1e9
print(f"embedding tables             {table_gb:,.0f} GB at {dim} floats per id, before optimizer state")

ad requests at peak          115,741 per second
pCTR predictions at peak     5.8 million per second (heavy model)
                             23.1 million per second (light model)
impressions / clicks per day 5 billion / 50 million
training rows per day        174 million after negative downsampling at 0.025
share of positives in rows   28.8% (was 1.0%)
embedding tables             128 GB at 16 floats per id, before optimizer state

• Requests: 5 billion ad requests a day, one ad shown each, is about 116,000 per second at a peak of twice the average.
• Scoring: a light model over 200 candidates and a heavy model over the best 50 means 23 million light and 5.8 million heavy predictions per second at peak.
• Training data: at 1 percent CTR that is 50 million clicks a day among 5 billion impressions. Keeping every click and 2.5 percent of non-clicks gives 174 million rows a day, 28.8 percent of them positive.
• Model size: 2 billion hashed feature ids with 16-float embeddings is 128 GB of tables before optimizer state. Embedding tables, not the dense layers, dominate memory.

Data and labels

An impressionOne showing of an ad to a user, logged with the features the model saw, the model version and the auction outcome. is the training row. The label is "clicked within some window", and here is the first design decision: there is no "did not click" event. A no-click label is only final once enough time has passed.

The Facebook ads paper (He et al., ADKDD 2014) describes this as an online joinerA streaming job that joins click events to the impressions they belong to, labelling an impression as a non-click only after a waiting window has passed.: impressions wait in a buffer for a fixed window. Too long a window delays training data and costs memory; too short loses late clicks, so some true clicks are labelled as non-clicks and the training CTR comes out biased low. The paper reports the bias can be cut to decimal points of a percent with a window whose memory cost is manageable.

Other label choices:

• Accidental clicks (a bounce in under a second) are often dropped or down-weighted.
• Conversions (install, purchase) arrive days later and are much rarer; they get their own model, pCVR, and the conversion probability is often predicted as pCTR x P(conversion given click).
• Position matters as in Design a feed ranking system : log the slot and treat it as a feature that is fixed to a reference value at serving time.

Features

Ad data is mostly sparse, high-cardinality featuresCategorical features with millions or billions of distinct values, such as user id, ad id, advertiser id, page URL or query, where each row has only a few non-zero entries.:

• Ids: user, ad, campaign, advertiser, creative, publisher site or app, placement.
• Context: time of day, device, country, page topic, query text for search ads.
• History counts: this user's CTR on this advertiser over 7 and 30 days, the ad's CTR in the last hour. The Facebook paper found that features capturing historical information about the user or ad dominate other types of feature.
• Content: embeddings of the ad image and text, so a brand-new ad is not a blank id.

Hashing ids into a fixed table

A model cannot keep a vocabulary of every URL ever seen. The hashing trickMapping a feature string to an index with a hash function modulo the table size, so new values need no vocabulary update and memory is fixed, at the cost of occasional collisions. maps each feature string to a row: index = hash("site=example.com") mod 2^k. New values need no vocabulary update and memory is bounded; collisions merge some unrelated values.

How small you can go is an empirical question. Google's ad click paper (McMahan et al., KDD 2013) reports that it could not hash its features down below several billion without observable loss, so it kept unhashed features. It reports other memory savings instead: half the unique features in some of its models occur only once in billions of examples, so adding a feature only after a counting Bloom filter has seen it a few times saves RAM at little cost, and so does storing weights in a 16-bit fixed-point encoding.

Feature crosses

A user's interest and an ad's category matter mostly together: a runner is likely to click a shoe ad, not a car ad. A linear model over separate ids cannot express that. A feature crossA feature that is the combination of two or more features, such as AND(user_interest=running, ad_category=shoes), letting a linear model learn interaction effects. creates a new id for the pair. The Wide and Deep paper's example is AND(user_installed_app=netflix, impression_app=pandora), which is 1 when a user who installed Netflix is shown Pandora. Crosses memorize specific co-occurrences well, but the number of possible crosses explodes, and a cross that never appeared in training has no weight at all.

Model choice and training

From logistic regression to deep models

Logistic regression on hashed ids and crosses was the workhorse for years: one weight per feature, sparse, fast, easy to update online. Google's 2013 system was a single-layer model with billions of coefficients, trained with FTRL-Proximal, an online algorithm with L1 regularization that produces sparse weights.

Trees plus a linear model. The Facebook paper fed boosted decision tree leaf indices into logistic regression. The combination beat either model alone by over 3 percent in normalized entropy (96.58 percent of the trees-only NE, against 99.43 percent for logistic regression alone).

Embeddings plus a deep network. Give every sparse id a learned embedding, concatenate them with dense features, and pass them through an MLP. Two ids that never co-occurred in training still get a sensible interaction, because each embedding was learned from other pairs. This generalizes, but can over-generalizeWhen a model with dense embeddings predicts interactions for pairs that are actually rare or irrelevant, because similar-looking embeddings suggest a link the data does not support. on niche pairs.

Wide and deep, and DCN

Wide and DeepA model that jointly trains a linear part over sparse features and crosses (memorization) and a deep network over embeddings (generalization), summing their logits before a single sigmoid. (Cheng et al., 2016) trains both at once: a wide linear part over sparse features and crosses, and a deep part over embeddings, whose outputs are added before one sigmoid:

where $\varphi (x)$ are the cross features and $a^{(L)}$ is the deep network's last hidden layer. In the paper's Google Play deployment, each categorical feature had a 32-dimensional embedding, the concatenation was about 1,200 dimensions, followed by three ReLU layers. The wide part was trained with FTRL and L1, the deep part with AdaGrad.

DCNDeep and Cross Network: a model that adds a cross network, whose layers explicitly multiply the input with the current layer to build feature interactions of increasing degree, alongside a regular deep network. (Wang et al., 2017) learns crosses instead of hand-writing them. Each cross layer computes

so layer $l$ contains every interaction of the input features up to degree $l+1$, with only $O(d)$ extra parameters per layer. On the Criteo display ads dataset (about 41 million records), DCN reached a test logloss of 0.4419 against 0.4428 for the same network without cross layers and 0.4474 for logistic regression; the authors note that 0.001 logloss is considered practically significant on that dataset.

Online training

Ads change by the hour: campaigns launch, budgets run out, a holiday starts. The Facebook paper found that going from weekly to daily retraining reduced NE by about 1 percent, and that the linear layer could be trained in near real time from the joiner's stream. Common setups:

• Warm-started batch retrains: the Wide and Deep paper's system, trained on over 500 billion examples, initialized each new model with the embeddings and linear weights of the previous one rather than training from scratch, and did a dry run before serving it.
• Continuous online updates: the model consumes the joined stream and pushes new weights to servers every few minutes, with anomaly checks that stop training if the stream's CTR suddenly drops (a broken click pipeline looks exactly like users who stopped clicking).
• Per-coordinate learning rates: rare features keep a high learning rate, common ones a low one. Google's paper gives ${\eta }_{t,i}=\alpha /(\beta +\sqrt{{\sum }_s{g}_{s,i}^2})$ and reports an 11.2 percent reduction in AucLoss against a global learning rate, where 1 percent is considered large.

High-level design

Deep dives

Deep dive 1: Crosses memorize, embeddings generalize

The sample below generates 1.35 million synthetic impressions. Clicks depend on user, ad and site biases plus an interaction between the user's interest group (30 groups) and the ad's category (40 categories). Most of the interaction is smooth and low rank, which embeddings can learn; 60 specific pairs have an extra one-off effect, which only a cross can memorize. A tenth of the group-category pairs never appear in training. Each model is trained with one streaming pass of per-coordinate AdaGrad, and scored with normalized entropyNormalized entropy: the model's log loss divided by the log loss of always predicting the average CTR. Lower is better; 1.0 means no better than the base rate. (NE), the Facebook paper's metric.

# Ad click prediction on synthetic logs: sparse ids, a feature cross, embeddings, downsampling and online updates.
import numpy as np

rng = np.random.default_rng(11)
U, A, S, G, C = 20_000, 3_000, 200, 30, 40          # users, ads, sites, interest groups, ad categories
grp, cat = rng.integers(0, G, U), rng.integers(0, C, A)
gv, cv = rng.normal(0, 1, (G, 3)), rng.normal(0, 1, (C, 3))
pair = 0.6 * gv @ cv.T                                # smooth, low-rank affinity: embeddings can learn it
quirk = rng.choice(G * C, 60, replace=False)          # 60 one-off pairs with a big extra effect
pair.flat[quirk] += 1.5                               # only a cross (memorization) can learn these
held = rng.choice(np.setdiff1d(np.arange(G * C), quirk), 120, replace=False)   # never in training
ub, ab, sb = rng.normal(0, .5, U), rng.normal(0, .5, A), rng.normal(0, .3, S)

def logs(n, ads=A, shift=0.0):
    u, a, s = rng.integers(0, U, n), rng.integers(0, ads, n), rng.integers(0, S, n)
    z = -4.6 + ub[u] + ab[a] + sb[s] + pair[grp[u], cat[a]] + shift * (cat[a] < 10)
    return u, a, s, (rng.random(n) < 1 / (1 + np.exp(-z))).astype(float)

class Model:  # logistic model over sparse ids, optional hashed cross, optional group/category embeddings
    def __init__(m, cross, emb, k=4):
        m.cross, m.emb = cross, emb
        m.w, m.nw = np.zeros(1 + U + A + S + 2**12), np.zeros(1 + U + A + S + 2**12)
        m.E = [rng.normal(0, .1, (G, k)), rng.normal(0, .1, (C, k))] if emb else None
        m.nE = [np.zeros((G, k)), np.zeros((C, k))] if emb else None
    def idx(m, u, a, s):
        cols = [np.zeros_like(u), 1 + u, 1 + U + a, 1 + U + A + s]
        if m.cross: cols.append(1 + U + A + S + (grp[u] * 7919 + cat[a] * 104729) % 2**12)   # hashed cross
        return np.stack(cols, 1)
    def predict(m, u, a, s):
        z = m.w[m.idx(u, a, s)].sum(1)
        if m.emb: z += (m.E[0][grp[u]] * m.E[1][cat[a]]).sum(1)
        return 1 / (1 + np.exp(-z))
    def fit(m, u, a, s, y, wt=None, lr=0.1, bs=1000):  # one streaming pass, per-coordinate AdaGrad
        wt = np.ones_like(y) if wt is None else wt
        for i in range(0, len(y), bs):
            b = slice(i, i + bs)
            g = (m.predict(u[b], a[b], s[b]) - y[b]) * wt[b]
            ix = m.idx(u[b], a[b], s[b])
            gw = np.bincount(ix.ravel(), np.repeat(g, ix.shape[1]), len(m.w))
            m.nw += gw**2
            m.w -= lr * gw / np.sqrt(m.nw + 1e-8)
            if m.emb:
                eu, ec = m.E[0][grp[u[b]]], m.E[1][cat[a[b]]]
                for t, (rows, other) in enumerate([(grp[u[b]], ec), (cat[a[b]], eu)]):
                    ge = np.zeros_like(m.E[t]); np.add.at(ge, rows, g[:, None] * other)
                    m.nE[t] += ge**2; m.E[t] -= lr * ge / np.sqrt(m.nE[t] + 1e-8)
        return m

def ne(p, y):  # normalized entropy: log loss divided by the log loss of always predicting the base rate
    ll = -np.mean(y * np.log(p) + (1 - y) * np.log(1 - p)); b = y.mean()
    return ll / -(b * np.log(b) + (1 - b) * np.log(1 - b))

tr = logs(1_500_000, ads=A - 500)          # the last 500 ads launch on day 2
keep = ~np.isin(grp[tr[0]] * C + cat[tr[1]], held)
tr = tuple(x[keep] for x in tr)
te = logs(300_000, ads=A - 500)
unseen = np.isin(grp[te[0]] * C + cat[te[1]], held)
print(f"training rows {len(tr[3]):,}, CTR {tr[3].mean():.2%}; test pairs never seen in training: {unseen.mean():.1%}")
for name, cr, em in [("ids only", 0, 0), ("ids + cross (wide)", 1, 0), ("ids + embeddings (deep)", 0, 1), ("wide and deep", 1, 1)]:
    p = Model(cr, em).fit(*tr).predict(*te[:3])
    print(f"  {name:24s} NE all {ne(p, te[3]):.4f}   seen pairs {ne(p[~unseen], te[3][~unseen]):.4f}"
          f"   unseen pairs {ne(p[unseen], te[3][unseen]):.4f}")

# Negative downsampling: keep every click and a fraction w of non-clicks, then recalibrate.
w = 0.025
ds = (tr[3] == 1) | (rng.random(len(tr[3])) < w)
m = Model(1, 1).fit(*(x[ds] for x in tr))
p = m.predict(*te[:3]); q = p / (p + (1 - p) / w)
print(f"downsampled to {ds.sum():,} rows ({ds.mean():.1%}); calibration = mean predicted / actual CTR")
print(f"  raw {p.mean() / te[3].mean():.2f}, recalibrated {q.mean() / te[3].mean():.3f}, NE recalibrated {ne(q, te[3]):.4f}")

# Day 2: 500 new ads launch and 10 of 40 categories gain 0.8 on the logit. Frozen model vs online updates.
day2 = logs(400_000, ads=A, shift=0.8)                            # one in six impressions is a new ad
frozen = Model(1, 1).fit(*(x[:1_000_000] for x in tr))
online = Model(1, 1).fit(*(x[:1_000_000] for x in tr))
hist_f, hist_o = [], []
for i in range(0, len(day2[3]), 20_000):  # progressive validation: predict a slice, then train on it
    b = tuple(x[i:i + 20_000] for x in day2)
    hist_f.append(ne(frozen.predict(*b[:3]), b[3])); hist_o.append(ne(online.predict(*b[:3]), b[3]))
    online.fit(*b)
print(f"day 2 progressive NE, last quarter: frozen {np.mean(hist_f[-5:]):.4f}, online {np.mean(hist_o[-5:]):.4f}")
print(f"day 2 calibration: frozen {frozen.predict(*day2[:3]).mean() / day2[3].mean():.2f}, "
      f"online {online.predict(*day2[:3]).mean() / day2[3].mean():.2f}")

training rows 1,349,088, CTR 2.18%; test pairs never seen in training: 10.0%
  ids only                 NE all 0.9662   seen pairs 0.9651   unseen pairs 0.9812
  ids + cross (wide)       NE all 0.9025   seen pairs 0.8877   unseen pairs 1.0602
  ids + embeddings (deep)  NE all 0.9283   seen pairs 0.9238   unseen pairs 0.9791
  wide and deep            NE all 0.8915   seen pairs 0.8814   unseen pairs 1.0008
downsampled to 62,498 rows (4.6%); calibration = mean predicted / actual CTR
  raw 17.84, recalibrated 0.976, NE recalibrated 0.8850
day 2 progressive NE, last quarter: frozen 0.8952, online 0.8649
day 2 calibration: frozen 0.88, online 1.00

• Ids only reaches NE 0.9662: the biases help a little, the interaction is invisible.
• Adding the cross (wide) drops NE to 0.9025 overall and 0.8877 on pairs seen in training, but on unseen pairs it is worse than the base rate (1.0602): the cross has nothing to say about a pair it has never seen.
• Embeddings (deep) are better than the cross on unseen pairs (0.9791) but worse on seen ones (0.9238), because they cannot memorize the one-off pairs.
• Wide and deep gets the best overall NE, 0.8915, and the best on seen pairs, 0.8814. On unseen pairs (1.0008) it is still weaker than embeddings alone: the shared training let the cross absorb what the embeddings would otherwise have learned. Real systems watch exactly this kind of slice.

Deep dive 2: Calibration sets the price

In a second-price auctionAn auction where the winner pays the smallest amount that would still have won, which for one slot is the runner-up's value. for one slot, ads are ranked by expected value per thousand impressions:

and the winner pays per click the smallest amount that keeps it on top: $\text{price}={\text{eCPM}}_2/(1000\times {\text{pCTR}}_1)$. Worked example: ad A bids 1.50 dollars with pCTR 2 percent (eCPM 30), the runner-up has eCPM 25, so A pays $25/(1000\times 0.02)=1.25$ dollars per click. Expected revenue per thousand impressions is $1.25\times 0.02\times 1000=25$ dollars.

Now suppose A's pCTR is overestimated at 4 percent. It still wins, but pays $25/40=0.625$ dollars per click while still being clicked at the true 2 percent: revenue halves, to 12.5 dollars. The general rule: revenue is the runner-up's eCPM times (true CTR / predicted CTR) of the winner. Miscalibration also decides who wins. If every pCTR is twice too high, every pay-per-click ad looks twice as valuable as a fixed-price CPM ad, so brand advertisers lose auctions they should win. This is why the Google paper calls calibrated predictions essential to run the auction, and why the Facebook paper tracks calibration (expected clicks divided by observed clicks) next to NE.

Fixing calibration. Google's paper fits a correction ${\tau }_d(p)$ per slice $d$ of the data: first a power law $\gamma p^{\kappa }$ fitted with Poisson regression, then a piecewise linear isotonic mapping, which reduced bias at both the high and low ends of the range. Check calibration per slice (country, device, ad format, new vs old ads), not only overall: an overall ratio of 1.00 can hide one slice at 1.3 and another at 0.7.

Deep dive 3: Negative downsampling and online learning

With 1 percent CTR, 99 percent of rows are non-clicks that teach little each. Keeping all clicks and a fraction $w$ of non-clicks cuts training cost, and the Facebook paper found the best NE at $w=0.025$. But the model now learns CTR in a world with 40 times fewer non-clicks, and its outputs are far too high. The paper's correction is

where $p$ is the prediction in the downsampled space. Worked example with $w=0.025$: a raw output of $p=0.288$ becomes $q=0.288/(0.288+0.712/0.025)=0.288/28.77=0.0100$, a 1 percent CTR. The second half of the sample shows the same: trained on 4.6 percent of the rows, the raw model predicts 17.84 times the real CTR on average; after the formula it is at 0.976, with an NE of 0.8850.

Online learning. The last part simulates day 2: 500 new ads launch (one in six impressions) and 10 of the 40 categories become more appealing. One model stays frozen; the other keeps learning from each slice after predicting it, which is the progressive validationEvaluating an online model on each new batch before training on it, so every example is used for both testing and training without leakage. Google's paper uses. By the last quarter of the day, the frozen model's NE is 0.8952 against 0.8649 for the online one, and the frozen model underpredicts by 12 percent (calibration 0.88) while the online model is at 1.00.

Try it

1. With no downsampling and no model error, A wins on its true value of 30 dollars per 1,000 and pays 1.25 dollars per click (the runner-up D has eCPM 25), for 25.0 dollars of revenue per 1,000 impressions.
2. Set downsampling to 2.5 percent with recalibration off. The model now predicts 19.4 percent for B, whose true CTR is 0.6 percent, and B wins with 80 percent efficiency and 22.2 dollars of revenue. The brand ad's 22 dollars looks tiny next to eCPMs of several hundred: it could never win. Turn recalibration on and A wins again with 25.0 dollars.
3. Turn downsampling off and raise the model error to 0.5. B's pCTR is now 1.65 times its true CTR, so B wins, pays 2.82 dollars per click and revenue falls to 16.9 dollars. Recalibration does not help here (try 10 percent downsampling with recalibration on): the formula fixes a known global distortion, not per-ad mistakes. That needs a better model and per-slice calibration checks.

Going deeper

Evaluation and experiments

Offline, use log loss or NE (always relative to a baseline on the same data, since absolute values move with the base CTR), AUC for ranking quality, and calibration ratios on many slices. Google's paper evaluates with progressive validation on the newest data and reports relative changes, since a click rate near 2 percent and one near 50 percent have very different best achievable log loss. Split by time, never randomly.

Online, a new pCTR model is an A/B test on revenue per thousand impressions, advertiser value (clicks and conversions per dollar spent) and user experience (ad hides, ad load, page latency). An improvement in offline loss that does not move these is not an improvement. The Wide and Deep paper shows the opposite case: an offline AUC gain of 0.002 over the wide-only model (0.728 vs 0.726) came with a 3.9 percent online gain in app acquisitions.

Monitoring

• Calibration per slice, hourly: predicted clicks over actual clicks. Alert on drift outside a few percent.
• The joined stream: CTR, volume and join coverage (share of clicks matched to an impression). A sudden zero CTR is a broken pipeline, not a market crash.
• Feature health: share of unseen ids, freshness of history counters, null rates.
• Business guardrails: revenue per thousand impressions, advertiser cost per click, share of auctions won by CPM vs CPC ads.

Bottlenecks and failure modes

Trade-offs we made

Extensions

• Multi-task heads for click, conversion and hide, combined in the auction, as in feed ranking ( Design a feed ranking system ).
• Bid shading and budget pacing, which use pCTR forecasts to spend each campaign's budget evenly through the day.
• Exploration for new ads: give them a small share of auctions with an uncertainty bonus, as in Multi-armed bandits .
• Privacy-preserving signals as user-level ids become less available: more weight on context and content features.

In the wild

Where you will see this: every ad network, search engine with sponsored results, social app and marketplace with promoted listings predicts click and conversion probabilities to price an auction. The same sparse-feature models power app store and product recommendations, and the Deep and Cross Network paper (Wang et al., 2017) is a common starting point for learned crosses.

Check yourself

Recap