Sparsity and the Hashing Trick

In one line: the features are almost all categorical with enormous cardinality, so the model is mostly a giant lookup table and only slightly a neural network.

The shape of the data

A single ad request's features: user id, ad id, campaign id, advertiser id, publisher, placement, device model, browser, operating system, country, city, hour, day of week, the user's recent interaction ids, the ad's category and creative id.

Almost all of them are categorical, and several have cardinality in the millions or billions. User id alone might be hundreds of millions. Represent that one-hot and a single request is a vector of billions of dimensions with a few dozen non-zero entries.

That last point reframes the engineering. The dense layers might be a few million parameters. The embedding tables can be hundreds of billions. So the memory, the sharding strategy and the serving latency are all dominated by the lookup, not by the arithmetic — which is the opposite of most deep learning systems.

Embeddings, and the long tail

Each categorical value maps to a dense vector, learned jointly with the rest of the model. Semantically similar values end up nearby, and a value seen once has a vector that is barely trained.

Which is the problem. The distribution of these values is extremely skewed: a small number of ads receive most impressions, and the majority appear a handful of times. Their embeddings are essentially random.

Two standard mitigations, and they are worth naming:

Frequency thresholding. Values seen fewer than N times map to a shared "rare" bucket rather than getting their own vector. Trading a specific-but-untrained embedding for a general-but-trained one is usually a gain.

Backing off to attributes. A rare ad id has almost no signal, but its advertiser, category and creative format do. Including those as separate features means a brand-new ad inherits a reasonable estimate from things like it — which is what makes ad cold start survivable at all.

The hashing trick

Even with thresholding, the vocabulary is enormous and it changes constantly — new ads and users appear every second. Maintaining an explicit id-to-index dictionary means a mutable, distributed, ever-growing map on the serving path.

The hashing trick removes it. Hash the feature value and take the result modulo a fixed table size:

index = hash(feature_name + ":" + value) mod TABLE_SIZE

No dictionary, fixed memory, and a value never seen before still gets an index. That last property is what matters operationally: a new ad id works immediately, with no vocabulary update and no deployment.

The cost is collisions — two distinct values landing on the same row and sharing an embedding.

What collisions actually cost

Less than intuition suggests, and the reason is worth knowing.

Because the value distribution is so skewed, most collisions are between two rare values, each with almost no signal. Merging two near-random embeddings loses very little. The damaging case is a collision between two frequent values, and that is rare precisely because frequent values are few.

The standard hedge is to give high-frequency values their own dedicated table and hash only the tail — a small dictionary for the head, hashing for everything else. That keeps the dictionary bounded and protects the values that matter.

Sizing the table is an empirical trade: larger means fewer collisions and more memory. The practical check is the load factor — distinct values divided by table size — and the observation that quality degrades gracefully rather than falling off a cliff as it rises.

Feature crosses, and why they matter here

A single feature says little. device = iPhone has some average click rate; ad_category = luxury_watches has another. What predicts a click is the combination — luxury watches on an iPhone in a particular country at a particular hour.

Classically these were built by hand: enumerate promising pairs, create a new categorical feature for each combination, add it to the model. It works and it explodes — crossing two features of a million values each gives 10^12 combinations, and only a tiny fraction ever occurs.

Hashing makes hand-crossing tractable, since the cross is just another string to hash. But it requires a human to guess which crosses matter, and the number of possible pairs is enormous.

Learning the interactions instead is what the model architectures in the next lesson are for.

Serving consequences

Three, and they are the practical reason this is a systems problem.

The table does not fit on one machine. Hundreds of billions of parameters means the embedding table is sharded across many machines, and a single inference gathers rows from several of them. That is a distributed read on the critical path, with an ads latency budget measured in tens of milliseconds.

The lookup is the latency. The dense forward pass is trivial. Most of the time is spent fetching embedding rows, which makes batching the lookup across candidate ads the highest-value optimisation — the same batched-multi-get point as feature stores, arriving from a different direction.

Updates must be incremental. You cannot redeploy a hundred-billion-parameter table hourly. So the table is updated in place, row by row, as training proceeds — which is why online learning is not merely convenient here but structural.

Next: learning the feature interactions instead of guessing them.