09 — Similar Listings

The task is the “similar listings” strip at the bottom of a vacation-rental listing page, built here from the definition of “similar” through to a served page of ten results.

Three conclusions come out of the build, each settled by arithmetic:

• the training signal has to come from what travellers browsed, not from what the listings look like;
• a model that has never been told what a “market” is can be ruined by the way its training examples are drawn;
• a catalogue of five million items ends up needing no search index at all.

An anchor listing goes in; ten listings the traveller could actually book come out. Everything between those two ends is the subject of the chapter.

The word “similar” has at least four defensible meanings that produce four different systems.

An embedding is a short list of numbers — a vector — attached to each listing, arranged so that two listings whose vectors point in nearly the same direction are the ones the system considers alike. Reaching straight for an embedding model skips the step that decides whether the embedding is trained on the right thing: deciding what “alike” is fitted to mean.

The first framing question is: similar in what sense — in price, in photos, in location, or substitutable for this specific trip? Those are different targets. Only substitutability has a booking as its optimum, and it is not recoverable from the listing’s attributes; it has to be learned from what people actually considered against each other. A hard constraint then shapes the retrieval design: a listing that is unavailable for the user’s dates has value exactly zero, so it is a filter, not a feature.

Two ideas from earlier chapters are restated here so this chapter stands on its own.

The first is two-tower retrieval: two separate small networks encode the two sides of a match — a query and an item, say — into the same vector space, so that matching becomes a geometry problem instead of a scoring problem. Two tower retrieval and why the separation is the whole point derives it at length.

The second is the vector index: a data structure that finds the nearest vectors to a query vector without comparing against all of them. Vector index internals derives its internals.

This chapter needs neither: there is only one tower, and the exact comparison is cheap enough that no index is worth building.

0. The model roster, the assumptions, and the deliberate absences

Before any model is derived, here is the whole roster: for each entry, what it consumes, what it produces, and the number that justifies it.

0.1 Every model in the system

Of the six rows below, two are models fitted on this problem, one is a pair of pre-trained models borrowed as feature extractors, and three are fixed arithmetic.

Two words used in the last column. Offline means the work happens on a schedule, hours or days before any user sees a page. Online means it happens inside the request, while the traveller waits.

One measurement recurs in the last column and is worth defining first. recall@100 is the share of test cases where the right answer appears somewhere in the top 100 results the system returns. The test cases here are real bookings:

1. Take a session that ended in a booking.
2. Feed the system the last listing the traveller looked at before booking — that is the query.
3. Check whether the listing they actually booked comes back in the top 100.

Held-out means those sessions were kept out of training, so the model has never seen them. A recall@100 of 0.44 therefore says: on 44% of real bookings, the system’s hundred candidates contained the booking.

The two rows that matter most are rows 1 and 2 — everything else is either borrowed or arithmetic.

0.2 What each stage assumes, and which assumptions carry weight

An assumption is load-bearing when the design changes shape if it is false, and merely convenient when a wrong value only moves a number.

0.3 What this system deliberately does not model

The absences are as informative as the roster, because each one is a decision with a derivation behind it.

• It does not predict the probability of a booking. There is no click-through-rate head and no calibration step, because nothing downstream multiplies the score by anything — only the order matters (The ml objective). The previous chapter’s central concern is simply absent from this one.
• It does not model availability. Whether a listing is free on the traveller’s dates is a hard filter, and An unavailable listing has value exactly zero derives why a feature cannot do that job.
• It does not model the viewer. There is no user tower and no user embedding: the anchor listing plus the inferred trip is the query. Personalization beyond the current session is deliberately out of scope.
• It does not model price, demand, or seasonal pricing. Price enters only as a filter and as one axis of the diversity re-rank.
• There is no second-stage ranking model. A cross-encoder reranker over the survivors is the obvious upgrade and is explicitly rejected, with the arithmetic, in Alternatives considered and rejected.
• There is no approximate nearest-neighbour index. The partition is already in the problem shows the exact comparison is cheaper than the approximation would be.
• It does not model complementarity — “you booked a cabin, here is a ski pass.” That is a different objective on differently-cut data, and Position in the funnel decides the target says so rather than pretending one model covers it.

1. Framing, and the four meanings of “similar”

The four candidate meanings of “similar” are not interchangeable, and the measurements below separate them — but first the module needs its inputs, its outputs, and the two catalogue numbers that later derivations depend on.

Start with the request and the response. The anchor listing is the listing whose page the traveller is currently reading; the module’s job is to fill the strip below it.

Three pieces of shorthand in that table are worth spelling out once.

• A market is a city or travel destination — Lisbon, or the Catskills. The platform has about 1,400 of them.
• p99 is the 99th percentile: the value that 99% of the population falls below. So “p99 42,000” means all but the largest 1% of markets hold fewer than 42,000 listings, and “p99 80 ms” means all but the slowest 1% of requests finish inside 80 milliseconds.
• Below the fold means the module renders further down the page than the traveller’s first screenful. That is why 80 ms is a comfortable budget rather than a tight one.

1.1 The two medians, and which one prices the system

The catalogue row hides a distinction that three later derivations depend on.

Market sizes are heavy-tailed: a few enormous markets sit far above a mass of small ones. The giveaway is in the table — the median market holds 900 listings but the mean is 3,600, four times larger, which only happens when a handful of huge values drag the average up.

A heavy-tailed distribution like this has two different medians, depending on what you count.

• Line up the 1,400 markets and take the middle one: it holds 900 listings. Most markets are small.
• Line up the 5,000,000 listings and ask how big a market each one sits in, then take the middle listing: it sits in a market of ~15,000. Most listings are not in the small markets, because each market contributes one entry to this list per listing it holds — so a 380,000-listing city contributes 380,000 entries and a 900-listing town contributes 900.

Both numbers describe the same catalogue. They differ by 17x.

The rule that picks between them: weight by whatever the thing you are counting is drawn from.

Apply it twice.

• A training pair is drawn from a listing, so negative sampling has to discriminate against a market of ~15,000 (Negative sampling and the derivation that decides the whole model).
• A request also arrives at a listing — the anchor is a listing whose page someone is reading, not a market someone picked off a list — so the serving-time scan is also priced at ~15,000, not at 900 (The partition is already in the problem).

So 900 is the right number for a statement about the catalogue (“most markets are small”) and the wrong number for any statement about traffic.

Everything downstream inherits the choice. The hard filters of Selectivity and why post filtering breaks let about 7.5% of a market through, so the eligible set at the median request is:

listing-weighted:   15,000 x 0.075  =  ~1,120 listings   <- the real eligible set
market-weighted:       900 x 0.075  =  ~68 listings      <- what the wrong median gives

That difference decides whether recall@100 means anything at all. Over ~1,120 candidates, “is the booking in the top 100” asks the embedding to rank it in the top 100 / 1,120 = 9%. Over 68 candidates, k = 100 is bigger than the entire set, so every candidate passes by definition, recall@100 measures the hard filter, and the embedding contributes nothing (Offline metrics).

1.2 Four meanings, and the measurements that separate them

Each row below is one candidate definition of “similar”: what you would have to train on to get it, and the case where it produces an obviously wrong answer.

A three-listing counterexample makes this concrete. A and B look nearly identical on every content signal and differ only in how many people they sleep; C looks unlike B on every content signal and is the one a family of six would actually take instead.

Listing A   $210/night, 200 m from B, same photographer, sleeps 2
Listing B   $215/night,                same photographer, sleeps 8

attribute similarity   HIGH        visual similarity   HIGH
geographic proximity   HIGH        substitutability    ZERO for a family of six

Listing C   $190/night, 1.2 km from B, different building, sleeps 8
attribute  MEDIUM   visual  LOW   geo  LOW   substitutability  HIGH

One anecdote does not settle a design, so here is the measured version. A decile is a tenth of a sorted population, so “the top decile of visual similarity” means the 10% of listing pairs that look most alike.

The block below asks the same question in both directions. The first group starts from pairs that look alike and asks how often users treat them as alternatives. The second group starts from pairs users do treat as alternatives and asks what else those pairs have in common.

pairs in the top decile of VISUAL similarity
   ... that are ever co-viewed in a session                    12 %

pairs in the top decile of CO-VIEW frequency
   ... within the same market                                  88 %
   ... within the same price band                              61 %
   ... in the top decile of visual similarity                  34 %

In the last line: of the pairs users most often weigh against each other, only 34% are in the top decile of looking alike. The other 66% — two-thirds — do not look alike at all.

The behavioral relation is not recoverable from the content relation. That is the empirical justification for training on sessions rather than on attributes.

2. The ML objective

Substitutability is so far a word, not a quantity; the first job is turning it into something estimable from logged events. Then comes the normalization convention that makes every vector operation in the chapter consistent, and the reason calibration, the previous chapter’s central concern, does not apply here.

Define substitutability operationally, so that every term corresponds to something the logs record:

Read P(X | Y) as “the probability of X, among the cases where Y was true.” Everything to the right of the bar is a condition the log has to be able to check.

sub(A, B)  =  P( user books B  |  user viewed A in this session,
                                  did not book A,
                                  B was available to them )

Each of the three conditions is there for a reason, and dropping any one of them changes what the number means:

• “In this session” fixes the trip — same dates, same city, same party (Data the session is the right unit and here is why).
• “Did not book A” is what makes this a substitution rather than a complement. Booking both is not one listing standing in for the other.
• “B was available” removes a confound: without it, B looks like a poor substitute whenever it was booked out, which is a fact about its calendar and not about the listing.

The normalization convention, stated once

Four differently-written vector operations later in the chapter are all the same operation, thanks to a single convention — and the one place that convention gets broken causes a real bug in Cold start and the content tower.

Four pieces of vocabulary first, in plain terms:

• The dot product of two vectors is what you get by multiplying them entry by entry and adding the results up. It is large when the two point the same way.
• The length (or norm) of a vector is the ordinary distance from the origin to its tip.
• The cosine between two vectors is their dot product divided by both lengths. Dividing strips out how long they are and leaves only how aligned they are, on a scale from -1 (opposite) through 0 (unrelated) to 1 (identical direction).
• L2-normalizing a vector means dividing it by its own length so the length becomes exactly 1. The result is a unit vector.

The key identity: for unit vectors, the dot product and the cosine are the same number. Dividing by 1 twice changes nothing. So the cheap operation the machine runs and the meaningful one you reason about coincide, and the serving code never has to compute a length.

Every listing vector that leaves the training job is L2-normalized, so the serving dot product is the cosine.

The same operation appears written four different ways; the table decodes all four.

The one place the convention is easy to lose is the cold-start blend. A convex combination of two vectors is a weighted average where the weights are non-negative and add to one.

A convex combination of two unit vectors is not itself a unit vector. Average two arrows pointing in different directions and you get a shorter arrow — the parts that disagree cancel. Index that shorter vector as-is and the dot product reads the shortfall as a score penalty, landing on exactly the listings that can least afford one (Popularity bias and hubness). Cold start and the content tower works the numbers.

Retrieval, not scoring — which is why calibration does not appear

The learning problem is to produce an embedding v per listing such that substitutable listings sit near each other under cosine. The module is then a nearest-neighbour query — find the vectors closest to this one — with constraints attached.

That is a different objective from ml-system-design/08, where the model’s output was a price and calibration was everything. Calibration means a predicted probability is literally true in the long run: among the impressions a model calls 3% likely, 3% actually convert. It matters whenever something downstream multiplies the number by money.

Here the score is a retrieval key. Only the order matters, and only within a market. Nothing downstream multiplies it, so calibration is irrelevant. What matters is knowing why calibration mattered in the previous chapter, not assuming it always matters.

3. Data: the session is the right unit, and here is why

With the objective fixed, the next question is what to train on. The right unit of training data is a single browsing session rather than a user’s whole history — one measurement settles it — and after that comes the choice between the two available labels, a co-view or a booking.

A session is an ordered sequence of listing-page views, cut on 30 minutes of inactivity or on a booking. “Cut on” means a new session starts whenever the traveller goes quiet for half an hour or completes a booking, so a session is a single sitting rather than an account’s lifetime.

Three numbers set the scale of the corpus:

median views per booking-intent session      28
sessions per month                          300 M
bookings per month                          7.2 M   (2.4 % of sessions)

The 28 there is the median of the booking-intent sessions only — the 2.4% that end in a booking. Across all sessions the figure is ~10 listing-page views (Framing and the four meanings of similar). Keeping those two apart matters in A booking is a strictly stronger relation than a view, where using the wrong one inflates a headline ratio eightfold.

The obvious alternative unit is the user’s lifetime history: longer, richer, more pairs per person. It is the wrong unit, because a user’s trips have different dates, party sizes, budgets and cities, and “alternatives for the same decision” is only true within one trip.

The block below measures that directly. Each row asks: given two listings drawn from the same session (left column) or from two different sessions of the same user (right column), how often do they share a property that a real alternative would have to share?

                                     same session   same user, diff. session
P(same market)                           0.91                0.34
P(same price band)                       0.61                0.29
P(same capacity band)                    0.78                0.41

Two listings in one session are in the same city 91% of the time. Two listings from the same person in different sessions: 34% — barely better than chance for someone who travels.

Within a session, intent is approximately constant; across sessions it is not. The session is the largest window over which “these are alternatives for the same decision” holds. A model trained on user-level co-occurrence learns “the same person looked at both,” which is a statement about the person, not about the listings.

3.1 A booking is a strictly stronger relation than a view

Within a session, the logs offer two kinds of pair — “these two were both looked at” and “this one was looked at and that one was booked” — and they are different relations. Perhaps surprisingly, the weaker one is the label to build on.

A co-view pair (A, B) is two listings both viewed in the same session. What it tells you is that both cleared the user’s filters — a symmetric set-membership relation, meaning (A, B) and (B, A) say the same thing and neither is ranked above the other. It is also partly a measurement of the search ranker that put them on the same results page, rather than of the user.

A (viewed A, booked B) pair says something stronger: B dominated A for that trip. That is an asymmetric ordering — the direction carries information — and it was produced by the user, not by the ranker.

Now measure how good each label is. Precision here is the fraction of pairs carrying a label that a human rater agrees really are substitutes, where the rater is asked “would a traveller take one instead of the other?” The first two rows are baselines to read the last two against.

The booking label is more than twice as precise. So why not just train on it? Because of volume.

Counting the pairs takes one piece of notation. C(10, 2) is the number of unordered pairs you can form from ten things: 10 x 9 / 2 = 45. A session of ten views therefore yields 45 co-view pairs. A booking-intent session has a median of 28 views, one of which is the listing that got booked, so it yields 27 (viewed, booked) pairs.

co-view pairs / month   =  300 M sessions x C(10, 2)  =  300 M x 45   =  1.35e10
view->book pairs        =  7.2 M bookings x 27        =              1.94e8
                                                          -----------------
                                             69x more co-views, at 2.3x lower precision

Both ratios in that last line, worked:

volume     1.35e10 / 1.94e8  =  69x more co-view pairs
precision  0.78    / 0.34    =  2.3x better on the booking label

Use the population rate of ~10 listing-page views per session (Framing and the four meanings of similar), not the 28 of a booking-intent session. Only 2.4% of sessions end in a booking, so pricing the whole corpus off the length of the rare ones is wrong — and wrong by a lot: C(28, 2) = 378 against C(10, 2) = 45 is 378 / 45 = 8.4x, so the naive read inflates the volume ratio from 69x to well over 500x.

69x the volume at 2.3x lower precision is a trade you take — provided you can also use the rare high-precision signal without diluting it into the common one. The architecture in The booking as a global context is exactly that.

3.2 Inferring the trip from the session — including when there is no trip

The request does not carry the traveller’s dates, party size or budget, so they have to come from somewhere — and a substantial fraction of page views reveal no dates at all, which forces a designed fallback rather than a shrug.

Every hard-filter argument in Business constraints and why they change the retrieval design rests on one input: the trip, meaning (dates, party size, price band). That input is never given by the request. The listing page carries an anchor and a session, not a booking form.

So the trip is inferred, and where it comes from decides what Business constraints and why they change the retrieval design can filter on.

The table lists the signals in precedence order — take the first one that is present, and only fall through when it is missing. The right-hand column is the one to watch, because the first row covers under two-thirds of traffic and the rest of this subsection is about the remainder.

The case the whole design has to survive is the one the table’s first row misses: a listing-page view with no dates at all. A direct link, a shared URL, an idle browse. That is the other ~38% of views.

With no dates there is nothing for Transpose the calendar and dates become free to AND against. Availability cannot be a hard filter here, because the thing it would filter on has not been expressed.

The design does not fabricate dates. It degrades the filter deliberately. The three-day availability AND is replaced by a single bookable-soon bit: does this listing have at least one free 2-night window in the next 60 days? That bit is precomputed per listing and refreshed nightly.

Compare the two filters by selectivity — the fraction of listings a filter lets through, so a high number means a loose filter:

specific 3-night window   selectivity 0.34    (the §6.2 number)
bookable-soon bit         selectivity ~0.90   (is this listing bookable at all)

The eligible set therefore widens by roughly 0.90 / 0.34 = 2.6x, and the price and capacity filters do all the narrowing instead.

The target slides too. Without dates, “substitutable for this trip” quietly becomes the discovery target of Position in the funnel decides the target — which is the honest thing to serve someone who has not told you a trip.

The Infer the trip node in Serving is this table plus this fallback. The dates that the entire Business constraints and why they change the retrieval design argument consumes are its output, not the request’s.

4. Session embeddings

With the data settled, the main model follows. One choice inside it — how negative examples are drawn — will turn out to decide whether the model learns anything useful at all.

The analogy is word2vec, term for term: a session is a sentence and a listing is a word.

word2vec is the classic method for learning word vectors from raw text. It slides a window along a sentence and fits each word’s vector so that it predicts the words appearing beside it. Words used in similar contexts end up with similar vectors, without anyone labelling anything.

Swap the nouns and you have this model. It learns one vector per listing so that listings appearing close together in the same session land close together in the space:

a sentence:   the   quick   brown   fox   jumped
a session:    L-771 L-8841  L-4127  L-993 L-2264

Two definitions carry the whole training loop:

• A positive pair is two listings viewed within a window of 5 positions of each other in one session. Meaning: “these two were weighed against each other.”
• A negative pair is a listing paired with one sampled from outside the session. Meaning: “these two were not.”

Training pulls positives together and pushes negatives apart. The booking as a global context then adds the booking as a positive for the whole session, and Negative sampling and the derivation that decides the whole model argues that the negatives are where the model is actually won or lost.

The output is a d = 32 unit vector per listing, L2-normalized at export (The ml objective).

flowchart TD
    S["Browsing sessions"] --> CV["Co-view pairs<br/>high volume, 0.34 precision"]
    S --> VB["Viewed-then-booked pairs<br/>low volume, 0.78 precision"]
    CV --> SG["Skip-gram training<br/>same-market + global negatives"]
    VB -->|booking as global context| SG
    SG --> EMB["32-dim behavioural embedding<br/>one unit vector per listing"]

4.1 The objective

The objective, written in full and then run on one pair so the gradient is a concrete number.

The objective is skip-gram with negative sampling, applied to session sequences instead of sentences. The name has two halves.

“Skip-gram” is the direction word2vec runs in: from a centre item, predict the items around it.

“With negative sampling” means the model is not asked to score all five million listings on every step. It is asked only to separate one true neighbour from a handful of randomly drawn impostors. That is far cheaper — and, as Negative sampling and the derivation that decides the whole model shows, it is where all the design risk lives.

Written as a loss — a quantity training pushes down — for a centre listing c, each context listing l inside a window of 5, and N = 5 sampled negatives n per positive:

L  =  - sum over (c, l)  [  log sigma(v_c · v_l)
                            +  sum over n in N negatives  log sigma(-v_c · v_n)  ]

Two symbols to unpack. sigma is the sigmoid, the S-shaped function 1/(1 + e^-z) that squashes any real number into the range 0 to 1 so it can be read as a probability. v_c · v_l is the dot product of the two listings’ vectors.

In plain English, that formula says: for every positive pair, push sigma(v_c · v_l) toward 1 — make the centre and its true neighbour agree. For every negative pair, push sigma(-v_c · v_n) toward 1, which is the same as pushing sigma(v_c · v_n) toward 0 — make the centre and the impostor disagree. Taking log of each and adding them up scores the whole batch; the outer minus makes it something to minimize.

The leading minus is not cosmetic. The bracket is a log-likelihood — the logarithm of how probable the observed data is under the current parameters — which you maximize; a loss is its negative, so L carries the sign and gradient descent, the procedure that repeatedly nudges each parameter in the direction that most reduces the loss, walks the parameters toward higher likelihood. Written without it, the same L is a quantity you would have to ascend, and calling it a loss is the sign bug.

That dot product is a logit — a raw, unbounded score that becomes a probability only after the sigmoid is applied to it — computed on unnormalized training parameters, and it is not a similarity. The convention in The ml objective applies to what is written to the index, and normalizing inside the loss would remove the magnitude that this style of training relies on: the optimizer expresses confidence by making vectors longer, and a unit-length constraint would take that channel away. Normalize once, at export.

Now one (c, l) pair computed end to end. The block below computes the loss twice: once where the model has the positive right, once where it has the same positive backwards, with the five negatives held fixed. The ratio between the two values is what the optimizer chases.

import math


def _sigma(z: float) -> float:
    return 1.0 / (1.0 + math.exp(-z))


# a single positive with five easily-separated cross-market negatives
_pos_logit = 4.0                                  # v_c . v_l, a true in-session neighbour
_neg_logits = [-3.0, -5.0, -2.5, -6.0, -4.0]      # v_c . v_n, negatives the model already separates

_pos_term = math.log(_sigma(_pos_logit))
_neg_term = sum(math.log(_sigma(-z)) for z in _neg_logits)
_loss_good = -(_pos_term + _neg_term)
print("well-fit pair      %.3f nat" % _loss_good)
assert 0.16 < _loss_good < 0.18                   # a well-fit pair costs ~0.17 nat

# now mispredict the positive: its logit flips sign, negatives unchanged
_loss_bad = -(math.log(_sigma(-4.0)) + _neg_term)
print("positive mispredicted  %.3f nat   (%.1fx)" % (_loss_bad, _loss_bad / _loss_good))
assert 4.1 < _loss_bad < 4.3                      # ~4.2 nat
assert _loss_bad / _loss_good > 20                # >20x the loss of the well-fit pair

A true neighbour at logit 4.0 against five easily-separated negatives costs about 0.17 nat; get that same positive wrong (logit -4.0) and it costs about 4.2 — more than twenty times as much. A nat is just the unit a loss built from natural logarithms is measured in, the way a bit is the unit when the logarithm is base 2; what matters is the ratio between the two numbers, not their absolute size. That ratio is the gradient the optimizer chases, and Negative sampling and the derivation that decides the whole model is the argument that on globally-sampled negatives it points almost entirely at “which market,” leaving nothing to learn about substitution within one.

The settings that produce that model: a vector width of d = 32, a context window of 5, 5 negatives drawn per positive, and 5 epochs — five complete passes over the training data.

The dimension is small on purpose. The useful within-market signal varies along only a few axes: price, capacity, style, sub-neighbourhood. A wider vector has spare capacity, and it spends that capacity on two bad things — memorizing individual listings, and hubness, the pathology where a handful of vectors end up close to everything and turn up in every result list (Popularity bias and hubness). d = 32 is also what puts the entire index on one machine (Serving).

4.2 The booking as a global context

The booking signal is rare and high-quality; the view signal is common and low-quality. Feeding the first into a model trained overwhelmingly on the second, without the good signal being averaged away, takes one structural change.

The skip-gram window encodes a locality prior — a built-in belief that items near each other in the sequence are related and distant ones are not. But a booking is the outcome of the entire trajectory — every listing viewed in that session lost to it, at any distance in the sequence. So for a session that ends in a booking, add the booked listing as a context for every position, not only for its window neighbours:

session:  v1 v2 v3 v4 v5 v6 ... v27  BOOK(b)

standard windows:      (v3, v1) (v3, v2) (v3, v4) (v3, v5) ...
+ global booking pair: (v_i, b)  for every i in the session

The relation being encoded is “was considered against and lost to,” which is precisely the relation the module needs to invert. Measured:

recall@100 on held-out (last-viewed -> booked) pairs
   windows only                       0.37
   + booking as global context        0.44        +19 %

# the +19% is relative, so it is worth showing rather than asserting
_recall_windows, _recall_booking = 0.37, 0.44
_booking_gain = (_recall_booking - _recall_windows) / _recall_windows
print("recall@100 %.2f -> %.2f  = %+.1f%% relative"
      % (_recall_windows, _recall_booking, 100 * _booking_gain))
assert abs(_booking_gain - 0.189) < 5e-3          # +19%, the table's figure

That is how the rare, high-precision signal gets injected without being averaged into the common one: it is a different kind of pair, not a re-weighted one.

4.3 Negative sampling, and the derivation that decides the whole model

Here is where the model is won or lost. The textbook way of choosing negative examples makes the training objective trivially satisfiable — the model learns geography and nothing else — and the fix falls out of two catalogue numbers.

The textbook default is to draw negatives uniformly from the global catalogue, or in proportion to freq^0.75 — each listing’s popularity raised to the power 0.75, a standard trick that keeps popular items over-represented among negatives, but less so than their raw frequency would.

Work out what that default is actually asking the model to do. A negative drawn uniformly from 5M listings lands in the anchor’s own market only as often as that market’s share of the catalogue:

catalog                                       5,000,000 listings
market of the typical listing (§1.1)             15,000 listings

P(a random global negative is same-market)  =  15,000 / 5,000,000  =  0.003
P(a random global negative is a DIFFERENT market)  =  1 - 0.003    =  0.997

99.7% of negatives are separable by market identity alone.

Follow that through the loss. A representation that encodes nothing but “which market” already drives sigma(-v_c · v_n) to ~1 on 99.7% of the negative terms, so log sigma(-v_c · v_n) is ~0 and those terms contribute nothing to L. The loss is essentially solved by a geo lookup.

In plainer terms: if almost every impostor is in a different city, a model that has learned only “which city” gets almost every question right. The loss stops falling. Training has no reason to go on and learn anything finer — and “anything finer” is the entire product.

That is the whole failure, and it shows up in the measurement exactly as predicted. Each row is one choice of where negatives come from. Within-market recall@100 is the Every model in the system test restricted to cases where the booked listing is in the same market as the anchor, which is the module’s actual job; cross-market is the same test restricted to cases where it is not.

Row 1 is the tutorial default and it is a 4x collapse on the column that matters: 0.09 against 0.37. Row 2 is the over-correction — a model that has never seen a global negative places all markets on top of each other, so it cannot tell Lisbon from Paris at all (0.12).

The module’s job is within-market substitution, so weight toward same-market negatives. But do not drop the global ones, because a second surface (“consider these nearby towns”) needs cross-market structure. Mix at 1:1 and pick the ratio from which surface you are optimizing, not from a default.

One more sampling detail is worth stating, because the exponent is not arbitrary. Drawing negatives in proportion to freq^0.75, the word2vec standard, flattens the popularity distribution without erasing it. Going to freq^1.0 over-samples popular listings as negatives and pushes them out of the space entirely, which costs tail quality; going to freq^0 under-samples them and worsens the hubness in Popularity bias and hubness.

4.4 What is actually being learned

What does the trained model return? Here is one anchor’s neighbour list; what is missing from it matters.

nearest neighbours of a $210 two-bedroom in a walkable district,
by cosine, before any business constraints:

  1. $195 two-bedroom, 1.1 km, different host, similar walkability
  2. $230 two-bedroom, 0.7 km
  3. $185 one-bedroom + sofa bed, 0.9 km
  4. $240 two-bedroom, 2.3 km, better transit
  ...

Note what is absent: no shared photographer, no shared amenity list, no shared host. The embedding recovered a substitution set, which is the thing that could not be computed from attributes.

The same anchor with its input row filled in: the fields the content tower of Cold start and the content tower consumes, with values.

Now score four candidates against that anchor, rank them, and re-rank them. The block uses one thing Popularity bias and hubness derives in full — CSLS, a correction that subtracts each listing’s local crowding r_k from the similarity, where r_k is that listing’s mean cosine to its own 20 nearest neighbours. A listing that sits close to everything has a high r_k and gets penalized for it.

In the output, L-9930 is second by raw cosine and last after the correction; that swap is the point.

# --- one anchor, one scored candidate list, and where each one ranked -------
ANCHOR = {"listing_id": "L-8841", "h3_cell": "8a2a1072b59ffff",
          "price_bucket": "200-224", "capacity": 4, "bedrooms": 2,
          "bathrooms": 1.0, "property_type": "apartment",
          "amenities": ("wifi", "kitchen", "washer", "heating"),
          "instant_book": True, "host_tenure_days": 1460, "n_sessions": 2310}

_blend_a = ANCHOR["n_sessions"] / (ANCHOR["n_sessions"] + 40.0)
assert abs(_blend_a - 0.983) < 5e-4        # warm: behavioural vector dominates

# cos is the section 6.3 exact dot product -- unit vectors, so dot IS cosine.
# r_k is each listing's MEAN cosine to its own 20 nearest neighbours, computed
# once at index build; at query time it is one array read (section 12.1).
_R_ANCHOR = 0.31
_CANDIDATES = [                       # id, description, cos, r_k
    ("L-4127", "$195 two-bedroom, 1.1 km",        0.912, 0.29),
    ("L-9930", "$230 two-bedroom, 0.7 km",        0.905, 0.52),   # a hub
    ("L-2264", "$185 one-bed + sofa bed, 0.9 km", 0.884, 0.27),
    ("L-7715", "$240 two-bedroom, 2.3 km",        0.877, 0.30),
]

def _csls(cos_xy, r_x, r_y):          # section 12.1, three additions and a lookup
    return 2.0 * cos_xy - r_x - r_y

_by_cos = sorted(_CANDIDATES, key=lambda c: -c[2])
_by_csls = sorted(_CANDIDATES, key=lambda c: -_csls(c[2], _R_ANCHOR, c[3]))

print("  id       %-30s   cos     r_k    CSLS    cos rank -> CSLS rank" % "candidate")
for cid, desc, cos, rk in _CANDIDATES:
    print("  %-8s %-30s %.3f   %.2f   %.3f       %d    ->  %d"
          % (cid, desc, cos, rk, _csls(cos, _R_ANCHOR, rk),
             [c[0] for c in _by_cos].index(cid) + 1,
             [c[0] for c in _by_csls].index(cid) + 1))

# the anchor's own r_k is the same for every candidate, so it shifts all four
# scores equally and cannot reorder them WITHIN one request -- it only matters
# when scores are compared ACROSS anchors.
assert len({round(_csls(c[2], _R_ANCHOR, c[3]) - _csls(c[2], 0.0, c[3]), 9)
            for c in _CANDIDATES}) == 1

# the adversarial case, which is the point: the hub is SECOND on raw cosine and
# LAST once its own crowding is subtracted. A test on L-4127, which wins under
# both, would have proved nothing.
assert [c[0] for c in _by_cos][:2] == ["L-4127", "L-9930"]
assert [c[0] for c in _by_csls] == ["L-4127", "L-2264", "L-7715", "L-9930"]
assert _csls(0.905, _R_ANCHOR, 0.52) < _csls(0.877, _R_ANCHOR, 0.30)

L-9930 is the row to read. On raw cosine it is second, 0.007 behind the winner. Its r_k of 0.52 says it sits 0.52 from its own twenty nearest neighbours on average — it is close to everything, which is what a hub is — and once that is subtracted it finishes last of four, behind a one-bedroom-plus-sofa-bed it beat by 0.021 on cosine. That single swap is the Popularity bias and hubness mechanism in one row: the hub was never being retrieved because it was a good match for this anchor.

5. Cold start, and the content tower

One population defeats the model of Session embeddings entirely: brand-new listings that nobody has browsed yet. Cold start is the standing name for this problem — a system that learns from behaviour has nothing to learn from on the day an item appears — and the answer here is a second model trained on what a listing looks like at birth, plus a rule for fading from one model to the other as browsing evidence arrives.

listings created in the last 30 days           8.0 % of live inventory
their share of session co-occurrences          0.4 %

Read those two lines together: new listings are 8% of what you can book and 0.4% of what the model has evidence about. That is a 20x under-representation in training data relative to inventory.

A listing with no sessions gets a randomly initialized vector, which is worse than useless — it is a random point in a space where distance means substitutability. It will be returned for anchors it has nothing to do with, and missed for the ones it matches.

The fix is a second model. Train an item content tower — a small network, one “tower” of the two-tower pattern, that maps a listing’s attributes into the same 32-number space — on the same session objective, consuming only features that exist at creation time:

• an H3 cell: a hexagonal geographic tile from Uber’s H3 grid, which is how a latitude and longitude become a categorical feature;
• price bucket, capacity, bedrooms, bathrooms, property type;
• an amenity multi-hot: one on/off flag per amenity, several of which can be on at once;
• the instant-book flag and host tenure;
• a photo embedding, and a review-text embedding when reviews exist.

Now measure it. Retrieval quality for a listing with zero sessions, over its first 30 days. Row 1 is the floor, the last row is the ceiling, and the two middle rows are the real comparison:

The content tower recovers 0.29 / 0.44 = 66% of warm quality on a listing that has never been viewed. That is why it is trained from the start rather than bolted on as a fallback. The nearest-3 average is the version people build first; it is half as good (0.14 against 0.29) and it inherits whatever geographic collapse (Geographic clustering collapse) is already in the space.

Fading from one vector to the other

Once a new listing starts getting browsed, you have two vectors for it and must combine them. Blend as evidence arrives, using the same shrinkage shape as everywhere else — shrinkage being the habit of pulling an estimate made from little data toward a safer default, by an amount that shrinks as the data grows:

v  =  normalize( a · v_behavioural  +  (1 - a) · v_content )
                                       a = n / (n + m),  m = 40 sessions

Here n is the listing’s session count and a is the weight on the behavioural vector. At n = 0, a = 0 and the vector is pure content; as n grows, a climbs toward 1 and the behavioural vector takes over.

m = 40 is not a round number someone liked. It is where the two recall curves cross: below 40 sessions the behavioural vector is noisier than the content vector, and above 40 it is better.

The block below computes a at three session counts to show the shape of the ramp:

# a = n/(n+m), m = 40: the blend weight itself, before any normalization
for _n_sess, _a_expected in ((5, 0.111), (40, 0.500), (100, 0.714)):
    _a_weight = _n_sess / (_n_sess + 40.0)
    print("n = %4d sessions -> blend weight a = %.3f" % (_n_sess, _a_weight))
    assert abs(_a_weight - _a_expected) < 5e-4

a climbs from 0.11 at 5 sessions, through 0.50 exactly at the m = 40 crossover, to 0.71 at 100.

Why the normalize in that formula is load-bearing

Dropping it manufactures the The two sided fairness loop death spiral out of nothing. The argument is four steps.

Step 1 — the blend is short. A convex combination of two unit vectors is shorter than either one (The ml objective), because the parts that disagree cancel. How short depends on a, and the shortfall is U-shaped: no shortfall at a = 0 or a = 1, worst at a = 0.5. Two vectors at cosine -0.10 — a typical random pair in d = 32 — give:

n =   5   a = 0.111   blended norm 0.885
n =  40   a = 0.500   blended norm 0.672   <- the bottom of the U
n = 100   a = 0.714   blended norm 0.743

Step 2 — a short vector scores low. The partition is already in the problem and the Serving SCAN node rank by dot product. A dot product scales with the length of both vectors, so an unnormalized blend multiplies the listing’s score by its own norm.

Step 3 — the penalty is a third of the score, at the worst possible point. A cold listing pointing in exactly the right direction scores 0.672 where a warm one scores 1.0. That is 1 - 0.672 = 33% of its score gone as a pure artifact of the shrinkage — and it peaks precisely at the m = 40 crossover this section is built around.

Step 4 — the penalty is self-sustaining. Lower score, fewer impressions, fewer sessions, n stays under 40, penalty persists.

Normalizing after the blend costs one square root per listing per index build.

The bottom of the U, where the §2 invariant actually breaks

The U-shape has a worst case worth naming.

At cosine -1.0 the two vectors are antipodal — pointing in exactly opposite directions. That happens when the two towers disagree completely: a listing whose photos and copy say “quiet studio for two” while its sessions say “party house for twelve.”

At a = 0.5 an antipodal pair cancels to the zero vector: 0.5 x v + 0.5 x (-v) = 0.

A zero vector has no direction, so there is nothing for a normalization to rescale. The naive implementation — divide by the norm unless the norm is zero, in which case return the input — hands it straight through to the index, where it scores 0.0 against every anchor forever. And a = 0.5 is n = m = 40, so this lands on exactly the crossover the section is built around.

The Popularity bias and hubness code handles it explicitly and asserts against the antipodal pair. A normalization that silently passes a zero vector is not a normalization.

6. Business constraints, and why they change the retrieval design

The embedding gives an ordering; the product’s hard rules decide what may be ordered at all, and they end up dictating the architecture. Availability must be a filter rather than a model feature, filtering after retrieval returns an empty module for the users who need it most, and by the end the search index has disappeared from the design entirely.

6.1 An unavailable listing has value exactly zero

Why can’t “is it free on these dates” be one more signal the model weighs? Two measured numbers settle it.

Compare what happens after a click on each kind of listing:

click on an AVAILABLE similar listing   ->  8.1 % book within the session
click on an UNAVAILABLE listing         ->  "not available for your dates"
                                            23 % abandon the session
                                            (baseline session abandonment: 6 %)

The upside of showing an unavailable listing is 0% — it cannot be booked, by definition. The downside is 23% - 6% = 17 percentage points of extra session abandonment.

A recommendation the user cannot act on has zero upside and a measurable downside, so no amount of similarity compensates for it. That makes availability a hard filter and not a feature. There is no similarity score at which those 17 points are bought back by a better match, because the better match cannot be booked.

That derivation is worth doing explicitly, because the instinct in a ranking system is to encode everything as a feature and let the model trade it off. The model cannot trade off a term whose value is identically zero; the arithmetic degenerates and the correct implementation is a filter.

6.2 Selectivity, and why post-filtering breaks

There are two obvious ways to combine a similarity search with hard constraints — retrieve then filter, or filter then retrieve — and pricing them shows the first one failing exactly on the queries with the most specific needs.

• Post-filtering: retrieve the most similar listings first, then throw away the ones that fail the constraints.
• Pre-filtering: narrow to the eligible listings first, then search only inside them.

To choose between them you need each constraint’s selectivity. Assuming the three constraints are roughly independent, the fractions multiply:

dates available for the requested 3-night window     0.34   (dates known; the §3.2 no-dates path relaxes this to ~0.90)
price band (the session's implied range)             0.40
capacity >= party size                               0.55
                                                     ------
combined, approximately independent                  0.075

Independence is an assumption, not a fact, and it is doing real work here — correlated constraints would multiply to something larger. The block below does the multiplication and then applies the same rate to both medians from The two medians and which one prices the system:

# the three constraints multiply because they are approximately independent
_p_dates, _p_price, _p_cap = 0.34, 0.40, 0.55
_combined = _p_dates * _p_price * _p_cap
print("dates %.2f x price %.2f x capacity %.2f = %.4f survive"
      % (_p_dates, _p_price, _p_cap, _combined))
assert abs(_combined - 0.0748) < 1e-4              # ~0.075 survivor rate
assert abs(100 * _combined - 7.48) < 1e-2          # 7.5 survivors from a top-100 post-filter
_over_retrieve = 10 / _combined * 3                # k to leave 10, with 3x headroom
print("top-100 post-filter leaves %.1f;  k for 10 with 3x headroom = %.0f"
      % (100 * _combined, _over_retrieve))
assert 395 < _over_retrieve < 405                  # ~400

# and what the SAME selectivity gives on the section 1 medians, which is where
# the market-weighted / listing-weighted distinction turns into a real number
for _label, _market in (("median market   (market-weighted)", 900),
                        ("median request  (listing-weighted)", 15_000)):
    print("  %s: %6d listings -> %7.0f eligible" % (_label, _market, _market * _combined))
assert abs(15_000 * _combined - 1122) < 1          # ~1,120: the section 10 figure
assert abs(900 * _combined - 67.3) < 0.1           # the 68 that a market-weighted read gives

So post-filtering the top 100 by cosine leaves 100 x 0.075 = 7.5 survivors for a 10-item module — already marginal. Over-retrieve instead: to leave 10 you need 10 / 0.075 = 133, and with 3x headroom that is k = 400. At the median request, post-filtering works.

The tail query is where it stops working. Take a traveller with specific needs, whose four constraints are each much tighter than the medians above:

8 guests, pet-friendly, hot tub, peak-season dates
   0.18 (peak dates) x 0.40 x 0.09 (capacity 8+) x 0.14 (pet + hot tub)
                                                  =  0.0009

post-filter the top 400  ->  E[survivors]      =  0.36
                             P(module empty)   =  e^-0.36  =  70 %

Two symbols there. E[survivors] is the expected number of survivors — the average you would see running that query many times — and it is just 400 x 0.0009 = 0.36. Then e^-0.36 = 0.70 is the probability of getting exactly zero survivors when the count behaves like a Poisson draw, the standard model for a small number of rare independent successes.

Seventy percent of the time, this traveller sees an empty module. The users with the most specific needs are the ones the design fails.

Below roughly 1% selectivity, post-filtering returns an empty module and pre-filtered graph traversal degenerates toward a linear scan — the collapse derived in When it is not fine say these unprompted. The prescription there was: partition instead of filtering.

6.3 The partition is already in the problem

The product already imposes a constraint — a substitute must be in the same city — and using it as the organizing key for the data turns out to remove the need for any approximate search structure.

Nobody substitutes Lisbon for Paris. Market is a hard constraint on the product and a natural shard key — the field you split the data by, so each piece of the system holds one market’s listings and a query only ever touches one piece. So partition the index by market.

Be precise about what that changes and what it does not. The selectivity is identical: none of the date, price or capacity constraints has anything to do with market membership, so the same 0.075 (or 0.0009 on the tail query) applies. What changes is the size of the set they act on: 5,000,000 / 15,000 = 333x smaller, and small enough to scan in full.

Run the tail query both ways:

global post-filter:   retrieve top 400 by cosine, apply filters  ->  0.36 survivors
market pre-filter:    scan all 15,000 in the market, apply filters
                      15,000 x 0.0009  =  ~14 survivors

Partitioning does not improve the filter. It removes the need to approximate before applying it.

Now price that full scan, because it turns out you do not need an index at all. Two terms: fp32 means each number is stored as a 32-bit floating-point value, four bytes. A FLOP is one floating-point operation, and comparing two 32-number vectors takes 32 multiplications and 32 additions, hence 64 of them.

The block below prices three scan sizes. The first group is the one that prices serving; the second is there only to show the shape of the catalogue. Each cost has two parts — reading the bytes and doing the arithmetic — and both are shown for the largest case.

32-dim fp32 UNIT vectors, so dot product = cosine = 64 FLOP

what a REQUEST scans (listing-weighted, section 1) -- this is the one that prices serving:
median request    15,000 listings    1.92 MB    ~35 microseconds

market-weighted statistics, for the shape of the catalogue:
median market        900 listings     115 KB     ~2 microseconds
p99 market        42,000 listings     5.4 MB    ~100 microseconds
largest market   380,000 listings    48.6 MB
      memory    48.6 MB @ 100 GB/s              0.49 ms
      compute   24.3 MFLOP @ 60 GFLOP/s         0.41 ms
                                                --------
                                                ~0.9 ms

Where those numbers come from, using the median request as the worked example:

bytes    15,000 listings x 32 dims x 4 B  =  1.92 MB
         1.92 MB / 100 GB/s               =  19 microseconds
FLOP     15,000 listings x 64 FLOP        =  0.96 MFLOP
         0.96 MFLOP / 60 GFLOP/s          =  16 microseconds
                                             --------------
                                             ~35 microseconds

The first row of that block is the one that prices the system, and the easy mistake is to use the second group. A request arrives at a listing, so the market it scans is drawn listing-weighted (The two medians and which one prices the system): the median request scans ~15,000 vectors at ~35 microseconds, not 900 at ~2.

That is 17x more work than the market-weighted reading suggests, and it changes nothing about the conclusion — which is the point. The design survives the correction by two orders of magnitude, and quoting the wrong median would have been a real error inside an argument that still came out right.

The largest market on the platform is a sub-millisecond exact scan, so there is no ANN index in this system.

ANN stands for approximate nearest neighbour: a family of data structures that find probably the closest vectors without comparing against every one, trading a little accuracy for a lot of speed. Approximation only pays once comparing against everything is too slow, which is above roughly 5M candidates per query. The worst market here is 380,000, which is 13x below that threshold.

This is the same conclusion as Why the geo index is the whole retrieval story, reached from partitioning rather than from geo filtering. The right response to “which ANN algorithm” is often “none”: the partition key you already have makes the candidate set small.

6.4 Transpose the calendar and dates become free

The date filter sounds like the expensive part. Store the availability data the other way round and it becomes almost free.

One term first. A bitmap here is one long row of bits, one bit per listing, where a 1 means “this listing qualifies.” Two bitmaps combine with a bitwise AND, a single machine instruction that keeps only the bits set in both — and one 64-bit AND processes 64 listings at once.

The naive layout stores a 365-bit calendar per listing. Filtering 380,000 listings for a 3-night window then means 380,000 scattered reads: one small jump into a different place in memory per listing, which is the slowest way to touch data.

Transpose it. Instead of one calendar per listing, keep one bitmap per day, over listings:

NAIVE (a calendar per listing)      TRANSPOSED (a bitmap per day)

L-0001: 0110111...  (365 bits)      Jul 4: 1011001...  (5,000,000 bits)
L-0002: 1001011...  (365 bits)      Jul 5: 1110011...  (5,000,000 bits)
L-0003: 1110001...  (365 bits)      Jul 6: 0111011...  (5,000,000 bits)
   ...  5M rows                        ...  365 rows

Now price the transposed layout. Each day’s bitmap is one bit per listing:

per day:   5,000,000 listings / 8  =  625 KB
365 days                           =  228 MB, fully resident

"free on Jul 4, 5, 6" = AND of three 625 KB bitmaps
   platform-wide:  234,000 x 64-bit ANDs        ~30 microseconds
   within one market shard (380k bits, 47.5 KB) ~2  microseconds

The 234,000 comes out of the width: 5,000,000 bits / 64 = 78,125 words per bitmap, and three bitmaps to AND together gives 78,125 x 3 = 234,375 instructions. Inside one market shard the same query touches 380,000 / 8 = 47.5 KB per day instead of 625 KB, which is why it drops to ~2 microseconds.

Transposing the calendar so listings are the bit axis turns date filtering into three bitwise ANDs. That is what lets availability be a cheap pre-filter instead of an expensive post-filter.

Price band and capacity get the same treatment — a bitmap per bucket, ANDed in. The whole constraint set costs microseconds, so An unavailable listing has value exactly zero’s “availability is a filter” is not just correct, it is free.

7. Position in the funnel decides the target

The module now has a model and its constraints; where it sits in the product decides what it should optimize. “Similar listings” is one of four places the same-looking module could appear — three of them want the model built above, and the fourth wants its opposite. A surface is one such placement in the product — a specific slot on a specific page.

The same embedding does not serve every surface, and knowing which one it fails on matters.

In the “Right target” column, three rows say substitution or something close to it; one says the opposite.

Three of the four are served by this embedding; the fourth needs a different objective entirely, because after someone books, the one thing they do not want is a substitute for what they just bought. For that surface, train on cross-session sequences — the exact signal Data the session is the right unit and here is why rejected — because there the user-level relation (“this person also takes ski trips”) is the right one. The two models are trained on the same logs cut at different boundaries.

8. Offline metrics

Before anything ships, model versions are compared offline. The measurement below climbed from 0.021 to 0.48 as the chapter’s design decisions stacked up; the more important point is the two things it cannot see.

Make the offline task be the production query. Take a held-out session that ended in a booking, use the last listing viewed before the booking as the anchor, retrieve k, and ask whether the booked listing is in the k.

Say which population the k is drawn from, because that is what decides whether the number means anything.

The production query scores the eligible set: the anchor’s market after the hard filters, which is ~1,120 listings at the median request (Serving). So recall@100 asks the embedding to put the booking in the top 100 / 1,120 = 9% of a set the filters already chose. What it measures is the embedding’s ordering.

Check every k against that number before quoting it. Suppose the eligible set had really been the 68 that a market-weighted median implies (The two medians and which one prices the system). Then k = 100 exceeds the whole candidate set, every candidate is in the top 100 by definition, and recall@100 measures the hard filter with the embedding contributing exactly nothing. It could not have read 0.44 — it would have read whatever fraction of bookings survive the date, price and capacity filters.

A recall@k whose k exceeds the candidate set is not a weak metric. It is not a metric at all.

The recall@10 further down is the one to read for the shipped page, because 10 is the number of slots.

Each line of the ladder below adds one design decision and keeps everything above it:

recall@100 on held-out (last-viewed -> booked) pairs

  random within market                                    0.021
  attribute nearest neighbour (price + capacity + geo)     0.11
  content tower only                                       0.29
  session skip-gram, global negatives only                 0.09   <- market-collapsed
  + same-market negatives, 1:1                             0.37
  + booking as global context                              0.44
  + content blend for items with n < 40 sessions           0.46
  + CSLS hubness correction (section 12.1)                 0.48

Two secondary measurements sit alongside it. The first is MRR, mean reciprocal rank: for each test case take one divided by the position of the correct answer and average those, so an answer at rank 1 scores 1.0 and one at rank 5 scores 0.2 — it is reported because the module shows only 10 results, so where in the list the booking lands matters, not just whether it is in the 100. The second is coverage, the share of the whole catalogue that ever appears in anyone’s top 10, which is the direct instrument for Popularity bias and hubness and The two sided fairness loop.

What this metric cannot see: the held-out pairs contain only listings the search ranker chose to show. Offline recall is therefore recall over the ranker’s candidate set, not over the catalog — the Why offline ranking metrics disagree with online ctr problem. The randomized slot in The two sided fairness loop is the only unbiased evaluation data, and it is worth building for that reason alone.

The whole ladder is measured before the diversity re-rank, and that is the tension with Geographic clustering collapse.

Every row above is recall@100 over the candidate set in cosine order. It answers “did retrieval contain the booking,” not “was the page we showed good.”

Two things act after the ladder is measured. MMR — maximal marginal relevance, a greedy re-ordering that picks each next item for a mix of how good it is and how unlike the already-picked items it is — and the host/300 m caps of Geographic clustering collapse. Both deliberately demote the same-street near-duplicates that raw cosine puts on top.

So the ladder actively rewards the geographic collapse Geographic clustering collapse calls a bug. The embedding that best reconstructs coordinates maximizes recall@100, because the held-out bookings are themselves drawn from what the search ranker showed, which is already collapsed onto the anchor’s block. The ladder cannot see the diversity that ships.

So measure at the shown slots instead, and on two datasets: the ordinary held-out logs, and the randomized slot of The two sided fairness loop, which is the only data in the system the logging ranker did not pre-select. Compare the columns, not the rows:

recall@10 of the booked listing
                             biased held-out logs   randomized slot (§12.5)
  cosine order, no diversity          0.30                    0.22
  after MMR + host/300 m caps         0.28                    0.29

On the biased logs, diversity reads as a small loss: 0.30 down to 0.28. On the unbiased data it is a clear gain: 0.22 up to 0.29. The unbiased number is the one that tracks the online +9.4% module booking rate (Geographic clustering collapse).

The ladder is a retrieval diagnostic, not the ship criterion. It says whether the candidate set contains the answer. Whether the page is good is settled by bookings per user (Online metrics and the ab) on data the logging ranker did not pre-collapse. That is the offline-online gap in this system: recall@100 rising to 0.48 while the shipped page trades top-of-list recall for coverage.

9. Online metrics and the A/B

Offline metrics compare model versions; live traffic is where the module is judged. An A/B test splits users at random into a control arm on the old system and a treatment arm on the new one, and compares them; the whole difficulty here is that the obvious thing to compare moves without anything getting better.

9.1 Module CTR is a cannibalization trap

A module can post a high click-through rate while adding nothing; one metric cannot be fooled that way. CTR is click-through rate, the share of impressions that get clicked; cannibalization is a gain that was taken from somewhere else in the same business rather than created.

Here is the failure in four lines. Both arms produce exactly one booking; only the path differs.

control:    user browses, books listing A directly.        1 booking
treatment:  user clicks the module, books listing B.       1 booking

module CTR                    0 %  ->  18 %
module-attributed bookings    0    ->  0.09 per session
PLATFORM bookings             unchanged

A similar-listings module can move a booking from A to B with zero net gain, and both module CTR and module-attributed bookings will call that a large win. So the headline is bookings per user, measured at the user level on a user-randomized experiment; module CTR is a diagnostic, and attribution is a reporting convention rather than a metric.

Where the 0.09 comes from.

The tempting check is 0.18 CTR x 8.1% booking rate = 1.5%, then calling 0.09 six times too big. That check is wrong, and the reason is units: it compares a per-session figure against a per-impression product.

A session carries ~10 listing-page views and the module renders on 40% of them (Framing and the four meanings of similar), so there are ~4 module impressions per session. Chain that through:

module impressions per session   10 views x 0.40 render   =  4
clicks per session               4 x 0.18 CTR             =  0.72
bookings per session             0.72 x 0.081             =  0.058

reported module-attributed bookings per session           =  0.09
                                                             ------
                                          the model is 1.5x low, not 6x

The load-bearing assumption there is the 4 impressions per session, not the CTR or the booking rate.

The residual gap is 0.09 / 0.058 = 1.5x. That is what attribution windows and multi-click sessions absorb: a session that clicks the module twice and books once counts as one booking against two impressions’ worth of denominator. Small enough to be a reporting convention rather than a modelling error.

The number that is easiest to compute describes a reporting convention rather than a measurement.

Now size the experiment for the metric you actually trust:

baseline bookings per user per 14 days      0.048
per-user sd (rare and bursty)               0.26
MDE 1 % relative                            0.00048

n per arm  ≈  16 sigma^2 / delta^2  =  16 x 0.0676 / 0.00048^2  =  4.7 M users

Three symbols there:

• sd is the standard deviation, the typical spread of a quantity around its average, written sigma in the formula. It is large here — 0.26 against a mean of 0.048 — because most users book nothing in a fortnight and a few book several times.
• MDE is the minimum detectable effect, the smallest true improvement the experiment is powered to notice, written delta. 1% relative on a baseline of 0.048 is 0.01 x 0.048 = 0.00048 in absolute terms.
• 16 sigma^2 / delta^2 is the standard sample-size rule for comparing two means at the usual significance and power settings.

Substituting: 16 x 0.26^2 / 0.00048^2 = 16 x 0.0676 / 2.3e-7 = 4.7e6. Detecting a 1% change in a rare, bursty behaviour costs 4.7 million users in each arm — and the denominator is squared, so halving the MDE to 0.5% would cost four times as many.

9.2 Guardrails, and the marketplace ones matter most

A guardrail is a metric you do not expect to improve and refuse to let get worse; on a two-sided marketplace the most important ones watch the supply side, which has no vote in the experiment.

9.3 Inventory interference

One effect is specific to marketplaces: the two arms of the experiment are not independent, because they are competing for the same rooms. Interference is the general term for one arm’s treatment changing the other arm’s outcome, which breaks the arithmetic every A/B test rests on.

Unlike a content feed, the inventory is consumed: a treatment arm that books a listing removes it from the control arm’s availability. At a 5% allocation in a median market this is negligible; at 50% in a tight market during peak season it is not, and the treatment effect will shrink on full rollout. Detect it by running a 5% arm and a 50% arm simultaneously and comparing the effect size — the same interference test as Online metrics and the ab, where the shared resource was an advertiser’s budget rather than a room.

10. Serving

Everything above now assembles into the path a single request takes — each stage priced in milliseconds, ending in the conclusion that the whole thing fits on one machine.

Solid arrows are the request path — everything a traveller waits on, from the top box to “10 listings.” Dotted arrows are the offline loop — the log becoming pairs, the pairs becoming a retrained model, the model becoming new embeddings. The one exception is the booking write at the bottom, which is solid because it must happen synchronously (Stale availability).

flowchart TD
    REQ(["Listing page view<br/>anchor listing · session"]) --> INT["Infer the trip<br/>dates · party size<br/>price band from session"]
    INT --> SHARD["Resolve market shard<br/>from the anchor"]
    SHARD --> BM["Constraint bitmaps<br/>AND 3 date bitmaps<br/>AND price band<br/>AND capacity"]
    BM --> SURV["Eligible set<br/>median request 1,120<br/>p99 market 3,100"]
    SURV --> EMB[("Embedding block<br/>32-dim fp32<br/>640 MB, whole catalog,<br/>resident on every node")]
    EMB --> SCAN["Exact dot products<br/>unit vectors: dot = cosine<br/>no ANN index"]
    SCAN --> CSLS["CSLS hubness correction<br/>2 cos - r_k(x) - r_k(y)"]
    CSLS --> RR["Business re-rank<br/>MMR over distance + price<br/>cap 2 per host<br/>cap 4 within 300 m"]
    RR --> EXP{"1 slot in 10<br/>reserved for cold<br/>listings, randomized"}
    EXP --> OUT(["10 listings"])
    OUT --> LOG[("Session log<br/>+ explore flag<br/>+ eligible-set size")]
    LOG -.->|daily| PAIRS[("Materialized pair store<br/>one day's log -> pairs<br/>26-week retention")]
    PAIRS -.->|weekly| TRAIN["Skip-gram retrain<br/>26-week window<br/>recency half-life 8 wk"]
    TRAIN -.->|embeddings| EMB
    BOOK(["Booking write"]) -.->|synchronous bit flip| BM

    style LOG fill:#1d3557,color:#fff
    style EMB fill:#2d6a4f,color:#fff
    style TRAIN fill:#40916c,color:#fff
    style BM fill:#bc6c25,color:#fff

The colours follow the key from The ladder, with the box each one lands on:

Two boxes deliberately lost their colour. The exact-scan node is uncoloured because it owns nothing and answers no read — it is arithmetic, and the whole of The partition is already in the problem is the argument that it is cheap enough not to be a component at all. And the reserved cold-listing slot is uncoloured because it had danger-red and did not deserve it: red means the rung you cannot undo, while that slot is a config change, is priced at 0.12% of bookings, and is a thing this chapter recommends (The two sided fairness loop). Painting the recommendation as the danger is backwards.

The request, box by box

1. A listing-page view arrives, carrying an anchor listing and a session. Nothing else — no dates, no party size.
2. Infer the trip from the session (Inferring the trip from the session including when there is no trip): dated-search parameters when the session carries them, and a bookable-soon bit — one free 2-night window in the next 60 days — when it does not. In the second case availability stops being a point filter and the target slides toward discovery (Position in the funnel decides the target). Everything downstream assumes this node’s output; nothing recovers if it is skipped.
3. Resolve the market shard from the anchor. The anchor’s market is the only market that will be touched.
4. AND the constraint bitmaps (Transpose the calendar and dates become free) to produce the eligible set: the listings that survive every hard filter.
5. Score the eligible set against the embedding block — the 32-dimensional fp32 vectors for the whole catalogue, 640 MB, held resident in memory on every serving node rather than fetched from anywhere.
6. Correct and re-rank: exact dot products, then CSLS (Popularity bias and hubness), then the business re-rank with MMR and the host and 300 m caps.
7. Reserve one slot in ten for a randomized cold listing (The two sided fairness loop), and emit ten listings.

Where the two eligible-set numbers in that box come from. At the median request it is ~1,120 listings: the median request scans a market of ~15,000 (The two medians and which one prices the system, listing-weighted, because a request arrives at a listing) and the Selectivity and why post filtering breaks constraints let 7.5% through, giving 15,000 x 0.075 = 1,120.

The 3,100 beside it is the p99 market — 42,000 listings — put through the same filter: 42,000 x 0.075 = 3,150. That is a floor rather than a ceiling on the p99 request, which is drawn from the same listing-weighted distribution. The honest upper bound is the largest market at 380,000 listings, which The partition is already in the problem prices at 0.9 ms unfiltered.

Below the output, the dotted arrows are the offline loop: the session log becomes a day’s pairs, the pairs accumulate for 26 weeks, and the weekly retrain writes new embeddings back into the block. The one solid arrow that does not come from the request is the booking write, which flips its availability bit synchronously (Stale availability).

The two fields hanging off the log node

Neither is decoration, so say what reads them.

The explore flag marks the one slot in ten that was randomized (The two sided fairness loop). It is the join key for the only unbiased evaluation set in the system. Without it, the randomized-slot column of the Offline metrics recall table cannot be computed at all.

The eligible-set size is the request’s post-filter candidate count. It is logged because it is the one number that says whether trip inference produced a real trip, and it moves in both directions:

• Up when the ~38% no-dates path (Inferring the trip from the session including when there is no trip) fires, because relaxing the date filter from 0.34 to ~0.90 widens the eligible set by ~2.6x.
• Down — collapsing — when a bitmap goes stale (Stale availability) or an inferred price band is too narrow. That shows up here before anyone notices an empty module, which is why it is a guardrail in Guardrails and the marketplace ones matter most.

Now the latency budget, which is also the reason there is no interesting distributed system here. p50 below is the median request:

infer trip from session (cached)                    0.10 ms
constraint bitmap ANDs                              0.02 ms
exact dot products, median 1,120 survivors          0.01 ms
                        p99   3,100 survivors       0.20 ms
CSLS correction (precomputed r_k per listing)       0.05 ms
business re-rank + MMR                              0.30 ms
                                                    --------
component sum                       0.48 ms p50,  0.67 ms p99
measured                            0.5  ms p50,  1.2  ms p99

The p99 gap is queueing at peak, not a stage. Every line above is a component sum, and the half-millisecond between 0.67 and 1.2 is the scheduler. Size the fleet on 1.2 ms.

Compare that against the budget set in Framing and the four meanings of similar: 1.2 ms measured against 80 ms allowed is roughly 65x of headroom. Nothing in this system is latency-constrained.

The whole retrieval index is under 1 GB, so every serving node holds a complete replica — an identical full copy rather than one slice of the data:

5M embeddings x 32 dims x 4 B     =  640 MB
365 daily calendar bitmaps        =  228 MB
metadata                          =  the rest
                                     -------
                                     under 1 GB

That one fact removes four things from the design: sharding; fan-out, sending one request to many machines; scatter-gather tail latency, waiting for the slowest of those machines to reply; and any consistency protocol to keep separate copies in agreement.

It is a direct consequence of choosing d = 32, and of a listing being a much smaller object than an ad-serving feature space (Features high cardinality categoricals at billions of values, 148 GB before optimization). It is the difference between a distributed system and a library.

11. Scale and cost

The traffic figures turn into a machine count and a yearly bill — and the surprise in the bill is that almost none of the money is buying arithmetic. QPS below is queries per second, how many requests the system handles each second.

300 M sessions/month x 10 listing-page views  =  3.0e9 views/month
module renders on 40 %                        =  1.2e9 requests/month
                                              =  460 QPS average
                                              ~ 1,600 QPS peak

1,600 QPS x 1.2 ms  =  1.9 cores of actual work

Two steps in that block are worth expanding. The average QPS is the monthly count spread evenly: 1.2e9 / (30 x 86,400 s) = 463. The peak figure applies a ~3.5x factor to that average, which is the usual shape for consumer traffic with a daily and weekly cycle. And the last line is Little’s law in its simplest form: 1,600 requests arriving each second, each occupying a core for 1.2 ms, is 1,600 x 0.0012 = 1.9 cores busy at any instant.

The fleet is not sized by compute. Two cores of arithmetic would fit on one machine.

What sets the node count is that each node carries the entire 1 GB index (Serving), so a node is a self-contained replica rather than a shard. You size for regional presence and for surviving the loss of a region, not for throughput. Twelve nodes in each of two regions is the smallest thing that does both — and those 24 machines are collectively doing under two cores of work.

The table below is the yearly bill. The bolded rates are the assumed prices; everything else is rate x units.

Two lines touch the pair data and they are not the same work — an easy place to bill twice.

The pair-generation pipeline is the daily job. It reads one day’s session log and materializes that day’s pairs into a store with 26-week retention — materialize meaning compute a result once and write it down, so later jobs read it instead of recomputing it.

The retraining line is the weekly job. It streams the accumulated 26 weeks of already-materialized pairs, shuffles them, builds the negative-sampling table, and fits.

Almost none of that eight-hour retrain is the model. The corpus is 8.4e9 training tokens — a token here being one listing occurrence in the pair stream — and five epochs over it is on the order of 5e14 FLOP, which is minutes of arithmetic. The eight hours is the shuffle and the streaming. The fit is free; the shuffle is the job.

One more trap in that table: the 24 in the pair-generation row is a coincidence of size, not the serving fleet. Those 24 serving replicas are already billed for all 8,760 hours on the first row, so charging them again would be double-counting. The pipeline runs on a transient batch pool that exists for three hours a day.

Two more lines are worth unpacking, because both are cases where the rate is real and the utilization is not.

Content tower inference is a reserved GPU that is idle 99.99% of the time.

Count the work. 400k new or changed listings a month is 400,000 x 12 = 4.8M a year. Each one needs a photo embedding over ~5 photos at 35 GFLOP apiece (Retrieval ranking and the arithmetic that sizes them), so 5 x 35 = 175 GFLOP per listing, with the small text encoder disappearing into the rounding.

4.8e6 listings × 175 GFLOP  =  8.4e17 FLOP
   at 300 TFLOP/s effective (H100)  =  2,800 GPU-s  =  0.78 GPU-hours/year
   0.78 × $2.50/GPU-hour            =  $2/year of arithmetic

what you actually pay:
   1 reserved H100 × 8,760 h × $2.50  =  $21,900/year

Two dollars of arithmetic on a twenty-two-thousand-dollar reservation. The GPU runs 0.78 hours out of 8,760, so it is idle 99.99% of the year. You are buying availability for a job that has to fire whenever a host edits a listing, not throughput. Same shape as the serving fleet at the top of this section.

The log line is storage, and storage has to name a volume, a retention window and a $/TB or it is a guess. All three, derived:

session + impression log
   3.0e9 listing-page views/month × 400 B/event        =  1.2 TB/month
   1.2e9 module impressions × 10 slots × 120 B/slot    =  1.4 TB/month
                                                          -----------
                                                          2.6 TB/month

   hot, 26 weeks (the training window, §12.3) = 6 × 2.6  =  16 TB
   cold archive, 24 months for backfill and eval        =  62 TB

   16 TB × $23/TB-month × 12                            =  $4.4 k/year
   62 TB × $4/TB-month  × 12                            =  $3.0 k/year
                                                          -----------
                                                          $7.4 k/year

Now compare that against the estimate you get without doing the derivation: a single round $70 k line covering storage and the pair-generation pipeline together, which would make data handling the largest cost in the system.

lumped guess               $70.0 k
derived  $7.4 k + $7.9 k = $15.3 k
                            ------
overstated by  70.0 / 15.3  =  4.6x

total with the guess   ~$160 k
total derived           $104.2 k

So the round number is wrong by 4.6x, not by an order of magnitude — and it moves the headline total by more than half. A round number for a line you have not derived is not conservative; it is wrong in whichever direction the round number happened to fall.

Where the bill actually sits, largest first: serving fleet $63.1 k, content tower $21.9 k, pair generation $7.9 k, storage $7.4 k, skip-gram retraining $4.0 k. Skip-gram retraining is the smallest line and storage is the fourth of five. The derivation did not make storage negligible; it made it ordinary.

That inverts the “compute is free” claim rather than strengthening it. The four compute-shaped lines are $63.1 + $4.0 + $21.9 + $7.9 = $96.8 k, which is 96.8 / 104.2 = 93% of the bill — against 56% in the version where a $70 k storage-and-pipeline row sits on top of them.

The bill is now almost entirely compute. What is free is the arithmetic. The content tower bills $21.9 k of reserved availability against $2/year of actual FLOPs. The 24-node serving fleet bills $63.1 k to do under two cores of work. You are not paying for computation; you are paying to have computers standing by, which is a different thing and has different levers.

The genuinely expensive things are off this table entirely: the offline evaluation harness and experiment time. With a 14-day booking window and 4.7M users per arm (Module ctr is a cannibalization trap), the experiment queue is the bottleneck — exactly as in Online and the timing problem that makes this chapter unusual.

The shape across three chapters is worth carrying into an interview: ml-system-design/07 cost $230k and was feature-store bound, ml-system-design/08 cost $5.4M and was latency bound, and this one costs $104k and is bound by nothing technical at all.

12. Failure modes

A design is not finished until it can name the ways it breaks in production. Each failure below gets a mechanism that explains why it happens, a detector that would catch it, and a control that fixes it — which is the shape an answer to “what goes wrong” should take.

12.1 Popularity bias and hubness

Why do a handful of listings end up in everyone’s results? Two mechanisms are at work, the second is the one people miss, and one correction fixes both at once.

Mechanism 1 — gradient volume. A popular listing appears in far more sessions, receives far more updates, and is pulled toward the centroid — the average position — of many different contexts. Its vector ends up near the middle of the space.

Mechanism 2 — high-dimensional geometry. In d dimensions, points nearer the centroid are the nearest neighbour of a disproportionate share of queries. This is hubness at work, and it happens because of the shape of high-dimensional space rather than because of anything in the data. It would appear even with random vectors.

top 1 % of listings by booking volume:
   share of top-10 module slots across all queries      34 %
   share of actual bookings                             11 %
                                                        ------
                                             3.1x over-exposed

The fix is CSLS, which stands for cross-domain similarity local scaling. The idea in one line: subtract each point’s local crowding from the similarity, so a listing that sits in a dense neighbourhood has to be genuinely closer to win.

r_k(z)  =  mean cosine from z to its k nearest neighbours
sim'(x, y)  =  2 cos(x, y)  -  r_k(x)  -  r_k(y)

The factor of 2 looks arbitrary until you regroup the terms:

2 cos(x, y) - r_k(x) - r_k(y)  =  [cos(x, y) - r_k(x)]  +  [cos(x, y) - r_k(y)]

Each bracket is “how much closer than usual is this pair, from one side’s point of view.” So CSLS is not measuring closeness; it is measuring closeness relative to how close each listing normally is to anything.

A hub sits close to everything, so its r_k is high and the correction penalizes it exactly in proportion to how hub-like it is. r_k is precomputed per listing at index build, so this costs one array read at query time.

The two rows below are the before-and-after. Notice that they move in opposite directions from what you would expect of a fairness intervention:

                                    before CSLS   after (k = 20)
top-1 % share of top-10 slots           34 %          16 %
recall@100 on held-out bookings         0.44          0.48

Hubness correction improves accuracy and exposure fairness simultaneously, which is rare enough to be worth saying out loud. The hubs were not being retrieved because they were good matches; they were being retrieved because of a geometric artifact. Removing them costs nothing and buys both.

The block below is the reference implementation of everything this chapter asserts about vectors: the CSLS formula, the normalization convention of The ml objective, the cold-start blend of Cold start and the content tower, and the bitmap pre-filter of Transpose the calendar and dates become free. The assertions at the bottom are the point — they run the antipodal case that produces a zero vector, which is the one an implementation quietly gets wrong.

import math


def csls(cos_xy: float, r_x: float, r_y: float) -> float:
    """Cross-domain Similarity Local Scaling. r_z is z's MEAN cosine to its own
    k nearest neighbours, precomputed at index build. A hub sits near everything,
    so its r is large and the correction penalizes it in proportion."""
    return 2.0 * cos_xy - r_x - r_y


def l2_normalize(v, eps=1e-12):
    """The section 2 convention, in one function: every vector that leaves the
    training job is a unit vector, so the serving dot product IS the cosine.

    A zero vector has no direction, so there is nothing to normalize. Returning
    it unchanged -- which is what `... if n > eps else list(v)` does -- is how
    the invariant in the docstring above gets broken silently: a zero-length
    vector leaves the training job, is indexed, and scores 0.0 against every
    anchor forever. Raise instead, and make the caller say what it means.
    """
    n = math.sqrt(sum(x * x for x in v))
    if n <= eps:
        raise ValueError("cannot L2-normalize a zero-norm vector: it has no direction")
    return [x / n for x in v]


def blend(v_behavioural, v_content, n_sessions: int, m: float = 40.0):
    """Cold-start blend, RE-NORMALIZED. m = 40 is where the two recall curves
    cross: below it the behavioural vector is noisier than the content vector,
    above it better.

    The re-normalization is the load-bearing line. A convex combination of two
    unit vectors is shorter than either one, and the shortfall is U-shaped in
    `a = n/(n+m)`: on two vectors at cosine -0.10 the norm is 0.885 at n = 5,
    **0.672 at n = 40**, and 0.743 at n = 100, worst exactly at a = 0.5.
    Section 6.3 and the section 10 SCAN node rank by dot product, so an
    unnormalized blend multiplies a cold listing's score by its own norm: a
    listing pointing in exactly the right direction loses a third of its score
    as a pure artifact, ranks lower, gets fewer sessions, and stays under
    n = 40. That is the section 12.5 death spiral, manufactured by a missing
    square root.

    The U-shape has a bottom, and at the bottom the norm is not merely small.
    Two ANTIPODAL unit vectors -- the two towers disagreeing exactly -- cancel
    to the zero vector at a = 0.5, which is precisely n = m = 40, the crossover
    this whole section is built around. `blend` is an export point, so without
    the branch below that zero vector is what gets indexed. Cosine -1.0 is rare
    and it is not impossible: a listing whose photos and copy say "quiet studio
    for two" while its sessions say "party house for twelve" is the shape that
    produces it, and it is exactly the listing a cold-start path should handle
    rather than delete.
    """
    a = n_sessions / (n_sessions + m)
    mixed = [a * b + (1.0 - a) * c
             for b, c in zip(v_behavioural, v_content)]
    if math.sqrt(sum(x * x for x in mixed)) <= 1e-12:
        # No direction survived the blend. Fall back to the side the shrinkage
        # already trusts more -- both inputs are unit vectors, so the fallback
        # is one -- rather than exporting a vector that scores 0.0 on every
        # anchor. Deterministic at a = 0.5, which is where this case lives.
        mixed = list(v_behavioural) if a >= 0.5 else list(v_content)
    return l2_normalize(mixed)


def eligible(date_bitmaps, price_bitmap, capacity_bitmap, nights):
    """Constraint pre-filter as bitwise ANDs over listing-indexed bitmaps.

    date_bitmaps maps a date -> int, where bit i is 1 if listing i is free that
    night. The transposed layout is what makes this microseconds instead of one
    scattered read per listing.
    """
    mask = price_bitmap & capacity_bitmap
    for night in nights:
        mask &= date_bitmaps[night]
    return mask


# --- the norm artifact, and the fix, executed ---------------------------
_COS = -0.0968                                   # a typical random pair in d=32
_B = [1.0, 0.0]
_C = [_COS, math.sqrt(1.0 - _COS ** 2)]


def _norm(v):
    return math.sqrt(sum(x * x for x in v))


def _dot(x, y):
    return sum(a * b for a, b in zip(x, y))


_UNNORMALIZED = {}
for _n, _expected in ((5, 0.885), (40, 0.672), (100, 0.743)):
    _a = _n / (_n + 40.0)
    _raw = [_a * b + (1.0 - _a) * c for b, c in zip(_B, _C)]
    _UNNORMALIZED[_n] = _norm(_raw)
    assert abs(_UNNORMALIZED[_n] - _expected) < 2e-3      # the shipped artifact
    assert abs(_norm(blend(_B, _C, _n)) - 1.0) < 1e-12    # the fix

# U-shaped, worst at n = m = 40, the crossover section 5 is built around
assert _UNNORMALIZED[40] < _UNNORMALIZED[5]
assert _UNNORMALIZED[40] < _UNNORMALIZED[100]

# a cold listing pointing in the anchor's direction must score 1.0, not 0.672
_a40 = 40 / (40 + 40.0)
_raw40 = [_a40 * b + (1.0 - _a40) * c for b, c in zip(_B, _C)]
_anchor = l2_normalize(_raw40)
assert abs(_dot(_anchor, blend(_B, _C, 40)) - 1.0) < 1e-12
assert abs(_dot(_anchor, _raw40) - 0.672) < 2e-3
assert _dot(_anchor, _raw40) < 0.68 * _dot(_anchor, blend(_B, _C, 40))

# and CSLS is defined on cosines, which is what the normalization guarantees
assert abs(csls(_dot(_anchor, blend(_B, _C, 40)), 0.31, 0.29) - 1.40) < 1e-9

print("unnormalized blend norm:  n=5 %.3f   n=40 %.3f   n=100 %.3f"
      % (_UNNORMALIZED[5], _UNNORMALIZED[40], _UNNORMALIZED[100]))
print("score penalty at the n = 40 crossover: %.1f%%"
      % (100 * (1 - _UNNORMALIZED[40])))

# --- the invariant, over ADVERSARIAL inputs ---------------------------------
# "Every listing vector that leaves the training job is L2-normalized" is a
# claim about every input, not about the convenient one above. The antipodal
# pair is the case that broke it: at a = 0.5 the convex combination is the ZERO
# vector, and a zero vector shipped to the index scores 0.0 against every
# anchor, forever. Test the worst case, not the confirming one.
_ADVERSARIAL = [
    ([1.0, 0.0], [-1.0, 0.0]),          # antipodal: cancels exactly at a = 0.5
    ([0.0, 1.0], [0.0, -1.0]),          # antipodal on the other axis
    ([1.0, 0.0], [1.0, 0.0]),           # identical: no shortfall at all
    ([1.0, 0.0], [0.0, 1.0]),           # orthogonal: the 1/sqrt(2) case
    ([0.6, 0.8], [-0.6, -0.8]),         # antipodal, off-axis
]
for _b, _c in _ADVERSARIAL:
    for _n in (0, 5, 40, 100, 10_000):
        _v = blend(_b, _c, _n)
        assert abs(_norm(_v) - 1.0) < 1e-12, (_b, _c, _n, _norm(_v))

# the antipodal pair at the crossover is the one that used to ship [0.0, 0.0]
_worst = blend([1.0, 0.0], [-1.0, 0.0], 40)
print("blend([1,0], [-1,0], 40) = %s   norm %.1f" % (_worst, _norm(_worst)))
assert _norm(_worst) == 1.0
assert _worst == [1.0, 0.0]            # falls back to the side a = 0.5 already trusts

# and l2_normalize itself now refuses rather than passing the zero vector on
try:
    l2_normalize([0.0, 0.0])
    raise AssertionError("l2_normalize returned a non-unit vector")
except ValueError:
    pass

12.2 Geographic clustering collapse

The most visible failure of the trained model is that every result is on the same street, and it comes straight from the geometry — which is what makes the fix a correction rather than a preference. Great-circle distance below is distance measured over the surface of the earth, the shortest path between two points on a sphere.

median great-circle distance from anchor to its top-10 neighbours:  180 m

Geography is the strongest predictor of co-view, so the embedding spends most of its capacity reconstructing coordinates and the module returns the same block.

ANCHOR:  $220 loft, Alfama district, Lisbon, sleeps 4

top 10 without diversity:
   all 10 in Alfama, 7 of them from 2 hosts, all $200-240,
   9 of 10 within 400 m

the user's actual booking:
   $190, 1.2 km away in Principe Real, sleeps 4  ->  rank 340

The module produced a photograph of one street, not a substitution set. Diversity here is not a taste preference; it is a correction for a representational artifact, and that framing is what makes it a defensible thing to hard-code.

Three fixes, stacked: same-market negatives (Negative sampling and the derivation that decides the whole model, which reduces the coordinate-reconstruction pressure at the source), MMR over (distance, price band, host) in the re-rank, and hard caps of 2 listings per host and 4 within 300 m.

                             before    after
median distance to top-10     180 m    1.4 km
module booking rate            —       +9.4 %

12.3 Seasonality

A model of travel behaviour goes stale faster than most, and the decay rate dictates the retraining schedule.

model trained on Jan-Mar sessions, recall@100 by evaluation month:
  Apr 0.44    May 0.41    Jun 0.36    Jul 0.29    Aug 0.26

Winter co-occurrence structure (ski towns, whole-house rentals, long stays) is not summer’s. Detection: the population stability index (PSI) — a single number summarising how far one distribution has drifted from another, computed here between the market-and-category mix of recent co-view pairs and that of the training window (Psi and kl computed). Control: weekly retrain on a 26-week trailing window with recency weighting at an 8-week half-life, plus an explicit same-period-last-year term so seasonal structure is available at the season boundary rather than relearned three weeks after it.

12.4 Host flooding and near-duplicates

Sometimes the model is right and the page is still useless, and the fix turns on getting one identifier keyed to the correct thing.

Consider a property manager with 12 identical studio units in one building. Users compare them constantly, so they co-occur constantly, so their embeddings are nearly identical, so they occupy the entire top 10. The module has correctly learned that they are substitutes and has produced a useless page.

Control: a near-duplicate cluster id keyed on the physical unit, with one representative shown per cluster. The key has three parts and deliberately excludes host:

• a building geohash — a short string encoding a small geographic tile, so nearby buildings share a prefix;
• capacity;
• a photo perceptual hash — a short fingerprint of an image that stays the same under resizing and re-compression, so the same photo re-uploaded still matches.

The separate hard cap of 2 per host sits alongside it.

Keying the cluster on host instead is the tempting mistake. It makes the id per-owner rather than per-unit, so the one pattern it most needs to catch — the same apartment listed by two management companies under two different host ids — ends up with two different keys and never collapses. Host belongs in the exposure cap, not in the identity.

Detection: the maximum single-host share of a top-10, tracked as a distribution rather than a mean, plus the count of top-10s where two distinct hosts share a unit-cluster id.

12.5 The two-sided fairness loop

A self-reinforcing loop quietly starves new listings, and one reserved slot — priced below — breaks it.

The loop runs like this: a new listing has no sessions, so it gets a content-only embedding at 0.29 recall against a warm listing’s 0.44, so it ranks lower, so it gets fewer views, so it still has no sessions. The supply side of the marketplace is the harder side to acquire, and this loop quietly suppresses it.

Price the intervention:

share of module bookings from slot 10                 2.4 %
booking rate of a cold listing vs a warm one          0.55x

cost of reserving slot 10 for a cold listing
   =  2.4 % x (1 - 0.55)  =  1.08 % of module bookings
module drives 11 % of platform bookings
   ->  0.12 % of platform bookings

benefit:  new-host median time-to-first-booking   31 d  ->  11 d
          new-host 90-day retention               +6 points

Two steps in that block are worth spelling out. The (1 - 0.55) is the loss, not the whole slot: a cold listing still books at 0.55x the warm rate, so you forfeit 45% of what slot 10 would have earned, not 100%. And the second multiplication just rescales module bookings to platform bookings: 1.08% x 11% = 0.12%.

0.12% of bookings buys a 2.8x faster supply ramp — 31 / 11 = 2.8 on time-to-first-booking — and the same randomized slot is the only source of unbiased evaluation data in the system (Offline metrics). Two payoffs from one slot, exactly as in Two sided exposure and the new organizer trap and ml-system-design/06 — which is the point: the exploration argument is the same in every recommender, and only the currency changes.

12.6 Stale availability

The cheapest possible mistake here — refreshing a filter on a timer — fails hardest on exactly the recommendations the system is best at.

If the calendar bitmap refreshes on a 5-minute schedule, the module shows listings booked in the last five minutes — and those are disproportionately the ones the module is best at recommending, so the failure concentrates on your best output. Flip the bit synchronously on the booking write path (it is one bit) and rebuild from the source of truth nightly to catch drift. Same argument as The staleness problem and why capacity is not a feature: a fast-moving hard constraint is read from the authoritative store, never from a feature snapshot.

12.7 Summary

Every failure above, on one page, in the mechanism-detection-control form. YoY in the last column means year-over-year: a term that compares the current week against the same week a year earlier.

13. Alternatives considered and rejected

Here are the designs that were on the table and the number that removed each one. Two entries name specific techniques: HNSW (hierarchical navigable small world) is the most widely used approximate-nearest-neighbour structure, a layered graph you walk downhill toward the query; a cross-encoder reranker is a second, slower model that reads the anchor and one candidate together and scores the pair, which is more accurate than comparing two independently-computed vectors and far more expensive.

14. Interviewer pushback

Eleven questions this design invites, each with the answer the chapter supports. The italic line under each question names what it probes for.

“Define similar.” Testing: whether framing is a habit. This is the question. There are four candidate definitions and they build different systems: similar in attributes, similar in photos, close by, or substitutable for this specific trip. Only the last one has a business optimum, because only a booking pays. And it is not recoverable from the other three — of pairs in the top decile of visual similarity, only 12% are ever co-viewed, and of pairs in the top decile of co-view frequency, only 34% look alike. So the target is P(books B | viewed A, did not book A, B was available), which is estimable from session logs, and the model is trained on behaviour rather than on content. The counterexample I would give is two listings 200 m apart at the same price by the same photographer, one sleeping 2 and one sleeping 8 — every content signal says similar, and for a family of six the substitutability is zero.

“Why sessions rather than the user’s whole history?” Testing: whether the unit of analysis was chosen or inherited. Because intent is only constant within a trip. Two listings in the same session are in the same market 91% of the time and the same price band 61%; two listings from the same user in different sessions are 34% and 29%. So user-level co-occurrence learns “the same person looked at both,” which is a statement about the person and not about whether the listings are alternatives. The session — cut on 30 minutes of inactivity or a booking — is the largest window over which “these compete for the same decision” is true.

“You have bookings, which are a much better label. Why train on views?” Testing: whether you can weigh precision against volume. Because the volume ratio is 69 to 1 and the precision ratio is only 2.3 to 1. A co-view pair has 0.34 precision against human judgement of substitutability; a viewed-then-booked pair has 0.78. But 300M sessions at ~10 listing-page views each give 1.4e10 co-view pairs a month against 1.9e8 view-to-book pairs — and I would use the population view rate there rather than the 28 views of a booking-intent session, because only 2.4% of sessions end in a booking and using the rare session’s length inflates the ratio eightfold. So I use co-views for volume and inject the booking as a different kind of pair rather than a re-weighted one: for any session that ends in a booking, the booked listing becomes a context for every position in the sequence, not just its window neighbours. The relation that encodes is “was considered against and lost to,” which holds across the whole trajectory. Measured, it takes recall@100 from 0.37 to 0.44.

“Walk me through your negative sampling.” Testing: whether you have trained one of these or read about one. This is where the model is won or lost. If negatives are drawn uniformly from the global catalog, then with 5M listings and a typical listing sitting in a 15,000-listing market, 99.7% of negatives are in a different market — so a representation that encodes nothing but market identity already drives the negative term to zero on 99.7% of the samples. The loss is solved by a geo lookup and there is no gradient left for within-market substitution. Measured, global-only negatives give within-market recall@100 of 0.09; mixing same-market negatives 1:1 gives 0.37. I keep the global ones because a second surface needs cross-market structure, and I set the ratio from which surface I am optimizing rather than from a default.

“Which ANN index?” Testing: whether you reach for the tool or the constraint. None, and I would want to explain why rather than just say it. Market is a hard product constraint — nobody substitutes Lisbon for Paris — so it is a free shard key. Inside a market, an exact scan at 32 dimensions is ~35 microseconds for the median request and 0.9 ms for the largest market on the platform at 380,000, split roughly evenly between memory bandwidth and arithmetic. I would say request deliberately: the median market holds 900 listings but the median listing sits in a market of ~15,000, a request arrives at a listing, and pricing the scan off the market-weighted median is the version of this answer that is 17x optimistic. ANN starts paying above about 5M candidates per query and the worst case is 13x below that. The alternative — a global HNSW with a metadata filter — is actively worse: my tail queries have 0.09% selectivity, post-filtering the top 400 leaves 0.36 survivors in expectation, and pre-filtered traversal degenerates toward a linear scan below about 1% selectivity. The right move at that selectivity is to partition, and the partition already exists.

“How do you handle availability?” Testing: whether hard constraints get modelled or filtered. As a hard pre-filter, and I would derive that rather than assert it. A click on an available similar listing books within the session 8.1% of the time; a click on an unavailable one hits a “not available for your dates” page and 23% of those sessions are abandoned against a 6% baseline. So the value of showing it is exactly zero and the cost is positive — there is no similarity score at which the trade-off flips, which means the model has nothing to learn and the correct implementation is a filter. Making it free is the interesting part: transpose the calendar so there is one bitmap per day over listings rather than one calendar per listing. Then “free on July 4, 5 and 6” is an AND of three 625 KB bitmaps, about 2 microseconds inside a market shard. Once the filter costs microseconds, the argument for pre-filtering stops being close.

“New listings have no sessions. What do they get?” Testing: whether cold start has an architecture or a patch. An item content tower trained on the same session objective, consuming what exists at creation time: H3 cell, price bucket, capacity, property type, amenities, host tenure, a photo embedding, a review-text embedding when there are reviews. On listings with zero sessions it gets recall@100 of 0.29 against 0.44 for a warm behavioural embedding — 66% of the quality — versus 0.14 for the thing most teams build first, which is averaging the three nearest listings by market, price and capacity. Then blend as evidence arrives with a = n/(n + 40), where 40 is where the two curves cross — and re-normalize the result, because everything downstream ranks by a dot product and a convex combination of two unit vectors is only 0.672 long at exactly n = 40, which would hand the coldest listings a 33% score penalty that has nothing to do with their direction. It matters more than the 8% inventory share suggests, because new listings are only 0.4% of co-occurrences, so without the content tower they are effectively invisible and stay that way.

“Module CTR went from 0 to 18% and attributed bookings are up. Ship it?” Testing: whether you take a good number at face value. No, because both of those numbers are consistent with zero value. If a user who would have booked listing A instead clicks the module and books listing B, module CTR and module-attributed bookings both go up and platform bookings do not move at all. That is not a hypothetical, it is the default outcome for a substitution module. So the headline is bookings per user, measured at the user level on a user-randomized experiment — 4.7M users per arm for a 1% MDE on a baseline of 0.048 bookings per user per 14 days. Module CTR stays as a diagnostic. And I would watch cancellation rate, because the way this feature actually loses is by substituting people into a worse match that books and then cancels.

“Everything it recommends is on the same street.” Testing: whether you can diagnose a representation from its output. Median distance from anchor to top-10 neighbour is 180 m, and that is a representational artifact rather than a preference. Geography is the strongest predictor of co-view, so the embedding spends most of its capacity reconstructing coordinates — the module produces a photograph of one street instead of a substitution set. Three fixes, stacked. Same-market negatives reduce the pressure at the source, because the model no longer gets credit for market identity. Then MMR over distance, price band and host in the re-rank. Then hard caps: two per host, four within 300 m, which also handles the property manager with twelve identical units in one building. That takes median distance to 1.4 km and module booking rate up 9.4%. The framing I would emphasize is that diversity here is a correction, not a taste — which is what makes it defensible to hard-code.

“A few listings dominate every result. Fix it.” Testing: whether you know hubness from popularity. Two mechanisms and the second is the one people miss. Popular listings appear in more sessions, get more gradient, and drift toward the centroid. And in high dimensions, points near the centroid are the nearest neighbour of a disproportionate share of queries regardless of the data — that is hubness, a property of the geometry. On my traffic the top 1% of listings take 34% of top-10 slots while accounting for 11% of bookings, so they are 3.1x over-exposed. CSLS fixes it: subtract each point’s mean cosine to its own k nearest neighbours from the similarity, so a point that is close to everything is penalized exactly in proportion to how hub-like it is. r_k is precomputed at index build, so it is one array read. Top-1% share goes 34% to 16% and recall goes 0.44 to 0.48 — accuracy and exposure fairness improve together, which tells you the hubs were never being retrieved because they were good.

“Where does calibration come in?” Testing: whether you apply the previous chapter or recite it. It does not, and that is the interesting answer. In ml-system-design/08, ad click prediction, the probability was multiplied by a bid and compared against a floor and a CPM bid, so a monotone rescaling of the score changed the outcome and cost real money. Here the score is a retrieval key: only the order matters, only within one market, and nothing downstream multiplies it. So I would spend zero effort on calibration and all of it on recall against held-out co-bookings and on the exposure distribution. Knowing which problem you are in is the point — calibration is not universally important, it is important exactly when something downstream consumes the magnitude.

15. Cheat sheet

Every load-bearing claim in the chapter, compressed to one line each, for the last read-through before an interview.

Next: 10 — Personalized News Feed — where the inventory is produced by the same people you are ranking for, so the ranking function becomes an input to next week’s candidate distribution.