Ninety Milliseconds to Predict a Click

I’ve spent the last few months trying to understand how ad serving actually works at scale, and I want to write down what I’ve pieced together, partly because it’s the most interesting engineering I’ve come across, and partly because writing it down is how I find out what I don’t understand.

Fair warning: there are several places below where the honest answer is that I’m still working through it.

The Clock Starts

Somebody loads a page. There’s an ad slot on it. What happens next has to finish before the page renders, which in practice means the whole thing gets around a tenth of a second, and by the time you account for network latency across the exchange, the part your system controls is more like ninety milliseconds.

In that window:

The publisher’s ad server sends a bid request to an exchange, formatted to the OpenRTB spec, which the industry has been converging on since 2010.
The exchange fans that request out to a set of bidders.
Each bidder looks up whatever it knows about the user and the context, estimates how likely this person is to click, converts that into a price, and responds.
The exchange runs an auction and the winner’s creative is returned.

If your bidder takes 150 milliseconds you don’t get a slower ad. You get no ad, because the auction closed without you. Timeouts are losses.

“The hard constraint isn’t accuracy. It’s that a perfect prediction delivered ten milliseconds late is worth exactly nothing.” — Sameer Gupta

What the Model Is

Here’s the thing that surprised me most, coming in with a vague sense that this must all be extremely sophisticated.

The workhorse is logistic regression. Not a neural network, not some proprietary marvel. The same technique a statistics course would teach you, applied to a feature vector with an absurd number of dimensions.

The sophistication is entirely in how you handle the scale.

The features are sparse and enormous. Every categorical thing gets its own dimension. This publisher. This ad. This browser. This hour of the day. This country. Then you take crosses of them, because “this ad on this site” behaves differently from either in isolation. The vector has billions of possible positions and, for any given request, a few hundred non-zero entries.

The hashing trick keeps it finite. You don’t maintain a dictionary mapping every feature string to an index, because that dictionary would be enormous and would need updating constantly. Instead you hash the feature string into a fixed-size space, say a couple of billion slots, and use that as the index. Two unrelated features occasionally collide and share a weight. It degrades performance slightly and it makes the whole thing tractable. I found this genuinely startling the first time I read it. The answer to “how do you index a billion features” turns out to be “you don’t, you just accept a small amount of corruption.”

Training is online, not batch. Rather than retraining nightly on everything, the model updates continuously as outcomes arrive. New ads and new campaigns appear constantly and a model trained on last week doesn’t know they exist.

Learning rates are per-feature. This is the part I find most elegant. A feature you’ve observed ten million times should barely move when you see it again. A feature you’ve seen twice should move a lot. So each coordinate carries its own accumulated history and scales its own step size accordingly. Vowpal Wabbit does this and is the tool I’ve spent the most time reading about.

L1 regularisation is doing double duty. It’s an accuracy technique, but at this scale it’s also a memory budget. It pushes weights to exactly zero, and a weight of exactly zero doesn’t need to be stored or shipped to the serving machines. Your model has to fit in RAM on every box in the fleet. Regularisation is what makes that true.

The Infrastructure Around It

The model is a small part of the system.

Overnight batch work runs on Hadoop, with Pig or Hive on top for the analysts. This is where features get computed over long histories.
Streaming updates flow through something like Storm, with Kafka increasingly used to move the event log around. Both are young. Kafka came out of LinkedIn last year and Storm was open sourced by Twitter around the same time.
Serving-time lookups hit memcached, because at ninety milliseconds a disk seek is out of the question. Everything the bidder needs at decision time must already be in memory somewhere within a couple of milliseconds of the network.
Everything is logged, because the log is the training data. The system’s own decisions become tomorrow’s model.

That last point is where I start getting out of my depth, and it’s the most interesting part.

Three Things I Don’t Properly Understand Yet

I said I’d be honest about this, so here it is.

The counterfactual problem. You only ever observe whether someone clicked on the ad you chose to show them. You have no data at all on the ads you didn’t show. So your training set isn’t a sample of the world, it’s a sample of your previous model’s opinions about the world, and every model you train inherits the biases of the one before it.

I understand why this is a problem. I do not yet understand what the correct fix looks like in production, beyond a general sense that you have to deliberately show some worse ads to find out what would have happened.

Explore versus exploit. Which follows directly. If you always show the ad with the highest predicted click rate, you never learn about the ones you’re underrating, and a new campaign with no history can never get enough exposure to prove itself. So you deliberately spend some fraction of your traffic on uncertain options.

I’ve been reading about Thompson sampling, where instead of taking your best estimate you draw from the distribution of what the true rate might be, and act on the draw. Chapelle and Li published an empirical evaluation of it last year that seems to show it works better than the alternatives. I follow the mechanics. I don’t yet have intuition for why it works as well as it apparently does.

Calibration versus ranking. This one took me embarrassingly long to see. In most classification problems you only care about the ordering. Here the predicted probability gets multiplied by the bid to produce a price in actual money. A model that ranks perfectly but predicts 0.02 where the truth is 0.01 will systematically overbid on everything and lose money at speed.

So the number itself has to be right, not just the ordering, and the standard evaluation metrics people reach for don’t capture that at all. Log loss does. Area under the curve does not, and I gather using the wrong one here is a common and expensive mistake.

What I Take From This

A few things that seem to generalise beyond advertising.

The clever part is usually the plumbing. I came in expecting exotic mathematics and found a textbook technique wrapped in extraordinary engineering. The value is in the feature pipeline, the latency budget, and the update loop.

Simple and fast beats sophisticated and slow, when there’s a hard deadline. A better model you can’t serve in time is not a better model.

Systems that learn from their own output need deliberate randomness, or they calcify around whatever they believed first. I suspect this generalises much more widely than advertising, to recommendation, to pricing, to anything where the system’s choices shape the data it later learns from.

Final Thoughts

I don’t work on these systems. I’ve been reading papers, documentation, and conference talks, and assembling a picture that I’m sure is wrong in places.

But I’ve found this more instructive than any general introduction to machine learning I’ve read, because it’s a complete system under real constraints, with real money attached, where every design decision has a visible reason. You can see why each piece is the shape it is.

If you know this material properly and I’ve got something wrong above, I’d genuinely like to hear it. I’m learning this in public, which is uncomfortable but seems to be the fastest way.