Recommendation, Ranking, and Personalization Questions

Direct answer

Build it as a funnel of four stages that each narrow the set and each get more expensive per item: retrieval pulls a few hundred candidates cheaply from two complementary indexes (lexical matching for what the query says, embedding similarity for who the user is), a learned reranker (a model that scores the short list using richer features) orders them, an exploration policy perturbs a small, safe part of the final page and records the probability of what it showed, and the logs from that policy train the next reranker and retrieval model. The stages interact through three contracts: retrieval sets the ceiling on recall, the reranker can only reorder what retrieval gave it, and exploration is the only part of the system that creates data about items the current model would never show.

Where to start

If you are new to this, learn the funnel first (cheap wide retrieval, then a precise reranker) and the idea that retrieval sets the ceiling. Then learn why every shown decision is logged with its probability. Embeddings with approximate search, the choice of ranking loss, and Thompson sampling or UCB are refinements you can add one at a time once that skeleton is clear.

Architecture

flowchart LR
  Q[Query + user id] --> U[Query understanding]
  U --> L[Lexical retrieval]
  U --> E[Embedding retrieval]
  P[User profile + session] --> E
  L --> M[Merge + dedupe]
  E --> M
  M --> R[Learned reranker]
  F[Feature store] --> R
  R --> X[Exploration slot]
  X --> O[Page returned]
  X --> G[Decision log with propensity]
  G --> T[Training for retrieval and reranker]

Stage by stage

1. Query understanding. Normalise and spell-correct the query; optionally classify intent. Output feeds both retrievers.
2. Candidate retrieval (recall stage).
   • Lexical: an inverted index (a map from each word to the documents containing it) scored with TF-IDF or BM25. TF-IDF weights each word by how often it appears in an item and discounts words that appear in many items ("the" counts for little, "skillet" for a lot); BM25 is a refinement that caps the credit for repeating a word and adjusts for the item's length. It guarantees that items containing the query's exact words are considered.
   • Embedding: an embedding is a vector of numbers learned so that nearby vectors mean similar items. The distance used is usually cosine similarity (the cosine of the angle between two vectors: 1 when they point the same way, 0 when unrelated). A two-tower model produces one for the user (history, session, profile) and one for each item; approximate nearest-neighbour (ANN) search over item vectors returns the items whose vectors are closest. This brings in items that do not share query words but fit the user.
   • Merge and de-duplicate; keep source labels because scores from different retrievers are on different scales and cannot be compared directly.
3. Learned reranker (precision stage). A model over (query, user, item) features: both retrieval scores and which source found the item, query-item text match, user-item affinity, item quality and freshness, and context (many of these come from a feature store, a service that serves precomputed per-user and per-item features at low latency). Trained with a ranking loss on clicks, purchases or other engagement. A pairwise loss looks at two items shown to the same user, one engaged with and one not, and penalises the model when it scores the engaged one lower: $\ln(1+e^{\,s_{\text{neg}}-s_{\text{pos}}})$ is small when the engaged item scores higher and large when it scores lower. A listwise loss looks at the whole list at once, for example by turning the scores into a softmax over the list and rewarding probability on the engaged items. Training adjusts the model's weights by gradient descent to lower this loss over many logged lists; the program below hand-sets three weights instead, and prints the loss for two example pairs. It sees a few hundred items, so it can afford expensive features and a larger model than retrieval could.
4. Exploration policy. The reranker's order is a greedy exploit choice. To learn about items it under-ranks, spend a small, bounded part of the page on exploration: for example, with probability $\epsilon$ the item in one lower-stakes slot is drawn uniformly from the ranks just below it. Or run Thompson sampling (draw a plausible value for each item from its uncertainty and rank by the draw) inside a top-K window; UCB instead ranks by the item's average plus a bonus that is larger the less the item has been shown. The exploration action must be recorded with its exact probability so later training and evaluation can reweight.
5. Logging and training loop. Log the query, user state, candidates, scores, shown order and the propensity (probability the system gave what it showed). Retrieval is retrained on engaged items, the reranker on shown-and-clicked data with position-bias correction (users click top slots more regardless of relevance).

How the pieces interact

• Retrieval bounds everything. An item retrieval misses can never be shown, so measure retrieval recall@K (the share of items users later engaged with that were in the candidate list of size K) separately from page quality.
• The reranker's training data comes from what it showed. It never sees outcomes for items it did not display, which makes the system drift toward its own past choices. Exploration is the correction, and the logged propensity lets the reranker be trained on reweighted examples.
• Exploration sits after the reranker, in a narrow window, because exploring before it would let random items displace strong ones and because the reranker is the best judge of what is safe to try. Limit it to lower slots and to items above a quality floor.
• Personalization enters twice: as the user vector in retrieval, and as user-item features in the reranker. Session signals (clicks in the last few minutes) update the user vector or the reranker features in real time; long-term profiles refresh offline.
• Latency is shared. Each stage gets a slice of the end-to-end budget (p99, the 99th percentile, means 99 percent of requests finish within that time); the reranker's candidate count is the main knob (fewer candidates, faster page, lower recall ceiling).

Worked example (small stand-ins)

The program below uses TF-IDF cosine similarity as a stand-in for the lexical index, hand-set topic vectors with exact dot products as a stand-in for a trained two-tower model and an ANN index, and a hand-set linear scorer as a stand-in for a learned reranker. A real system would put a BM25 or inverted index, a trained two-tower model with ANN search, and a model trained on logged engagement in those places. The latency numbers are an assumed allocation for a 150 ms 99th-percentile target, not measurements.

import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity

# Catalog: (title text, topic vector [footwear, outdoor, kitchen], popularity count)
items = [
    ("trail running shoes lightweight", [0.9, 0.5, 0.0], 900),
    ("road running shoes cushioned", [1.0, 0.1, 0.0], 1500),
    ("running socks merino", [0.6, 0.3, 0.0], 400),
    ("waterproof hiking boots", [0.8, 0.8, 0.0], 700),
    ("running belt hydration", [0.1, 0.6, 0.0], 300),
    ("cast iron skillet", [0.0, 0.1, 1.0], 1200),
    ("camp stove compact", [0.0, 0.8, 0.5], 500),
    ("sprint spikes track shoes", [0.9, 0.2, 0.0], 150),
    ("non stick frying pan", [0.0, 0.0, 1.0], 1100),
    ("trail running vest pack", [0.2, 0.9, 0.0], 350),
]
texts = [t for t, _, _ in items]
E = np.array([v for _, v, _ in items], float)
E = E / np.linalg.norm(E, axis=1, keepdims=True)         # unit vectors: cosine == dot product
pop = np.array([p for _, _, p in items], float)

tfidf = TfidfVectorizer().fit(texts)
X = tfidf.transform(texts)


def retrieve(query, user_vec, k_lex=5, k_emb=5):
    q = tfidf.transform([query])
    lex = cosine_similarity(q, X).ravel()                # stand-in for BM25 / inverted index
    emb = E @ (user_vec / np.linalg.norm(user_vec))      # exact search stand-in for an ANN index
    lex_ids = [i for i in np.argsort(-lex)[:k_lex] if lex[i] > 0]
    emb_ids = list(np.argsort(-emb)[:k_emb])
    cands = sorted(set(lex_ids) | set(emb_ids))
    return cands, lex, emb


def rerank(cands, lex, emb, w=(2.0, 1.5, 0.3)):
    # hand-set linear scorer: a stand-in for a learned reranker over the same three features
    f = np.stack([lex[cands], emb[cands], np.log1p(pop[cands]) / np.log1p(pop.max())], 1)
    s = f @ np.array(w)
    order = np.argsort(-s, kind="stable")
    return [cands[i] for i in order], s[order]


def explore(ranked, rng, slot=2, window=5, eps=0.2):
    # epsilon-slot: with prob eps, the item in `slot` is drawn uniformly from ranks slot..slot+window-1
    pool = ranked[slot:slot + window]
    out = list(ranked)
    chosen = ranked[slot]
    if rng.random() < eps:
        chosen = pool[rng.integers(len(pool))]
        out.remove(chosen); out.insert(slot, chosen)
    prop = {it: eps / len(pool) + ((1 - eps) if it == ranked[slot] else 0.0) for it in pool}
    return out, chosen, prop


user = np.array([0.2, 1.0, 0.1])          # an outdoors-leaning user (e.g. mean of clicked item vectors)
cands, lex, emb = retrieve("running shoes", user)
ranked, scores = rerank(cands, lex, emb)
print("candidates (lexical U embedding):", [texts[i] for i in cands])
print("final order before exploration:")
for r, (i, s) in enumerate(zip(ranked, scores)):
    print(f"  {r}: {texts[i]:34s} score {s:.3f}")
out, chosen, prop = explore(ranked, np.random.default_rng(3))
print("slot 2 item served:", texts[chosen])
print("logged propensities for slot 2:", {texts[k]: round(v, 3) for k, v in prop.items()})
print("propensities sum to 1:", round(sum(prop.values()), 6))
print("cosine == dot for unit vectors:", bool(np.allclose(cosine_similarity(E[:3], E[3:5]), E[:3] @ E[3:5].T)))

# latency budget: an assumed allocation of a 150 ms p99 end-to-end target, not a measurement
budget = {"query understanding": 10, "lexical retrieval": 20, "ANN retrieval": 25, "feature fetch": 25,
          "rerank 200 candidates": 40, "exploration + logging": 5, "network and slack": 25}
print("assumed stage budgets (ms):", budget, "sum =", sum(budget.values()))

# Where the reranker scores come from: score = 2.0*lexical + 1.5*embedding + 0.3*popularity
print()
print("features (lexical cosine, embedding dot, scaled popularity) and score for the ranks 0 to 3:")
for i in ranked[:4]:
    f = [lex[i], emb[i], np.log1p(pop[i]) / np.log1p(pop.max())]
    print(f"  {texts[i]:34s} {np.round(f, 3)} -> {float(np.dot(f, (2.0, 1.5, 0.3))):.3f}")
loss = lambda s_pos, s_neg: float(np.log1p(np.exp(s_neg - s_pos)))
print("pairwise loss if the vest pack (2.155) was clicked and the shoes (2.420) were not:", round(loss(scores[2], scores[0]), 3))
print("pairwise loss if the shoes (2.420) were clicked and the road shoes (1.854) were not:", round(loss(scores[0], scores[3]), 3))
print("random number for the exploration test:", round(float(np.random.default_rng(3).random()), 3), "(exploration fires only below 0.2)")

Output:

candidates (lexical U embedding): ['trail running shoes lightweight', 'road running shoes cushioned', 'running socks merino', 'waterproof hiking boots', 'running belt hydration', 'camp stove compact', 'sprint spikes track shoes', 'trail running vest pack']
final order before exploration:
  0: trail running shoes lightweight    score 2.420
  1: running belt hydration             score 2.209
  2: trail running vest pack            score 2.155
  3: road running shoes cushioned       score 1.854
  4: running socks merino               score 1.645
  5: camp stove compact                 score 1.574
  6: waterproof hiking boots            score 1.511
  7: sprint spikes track shoes          score 1.426
slot 2 item served: trail running vest pack
logged propensities for slot 2: {'trail running vest pack': 0.84, 'road running shoes cushioned': 0.04, 'running socks merino': 0.04, 'camp stove compact': 0.04, 'waterproof hiking boots': 0.04}
propensities sum to 1: 1.0
cosine == dot for unit vectors: True
assumed stage budgets (ms): {'query understanding': 10, 'lexical retrieval': 20, 'ANN retrieval': 25, 'feature fetch': 25, 'rerank 200 candidates': 40, 'exploration + logging': 5, 'network and slack': 25} sum = 150

features (lexical cosine, embedding dot, scaled popularity) and score for the ranks 0 to 3:
  trail running shoes lightweight    [0.587 0.645 0.93 ] -> 2.420
  running belt hydration             [0.242 0.995 0.78 ] -> 2.209
  trail running vest pack            [0.211 0.995 0.801] -> 2.155
  road running shoes cushioned       [0.558 0.291 1.   ] -> 1.854
pairwise loss if the vest pack (2.155) was clicked and the shoes (2.420) were not: 0.834
pairwise loss if the shoes (2.420) were clicked and the road shoes (1.854) were not: 0.45
random number for the exploration test: 0.086 (exploration fires only below 0.2)

Reading the output: for the query "running shoes" from an outdoors-leaning user, the lexical side surfaces the running items, while the embedding side adds camp stove compact and waterproof hiking boots, which share no query word with the query. The reranker puts trail running shoes lightweight first, and running belt hydration second, above the popular road running shoes cushioned, because the user vector counts for more than the popularity feature. Exploration then acts only on slot 2: with probability 0.2 the item there is replaced by one of the five items in ranks 2 to 6 (uniformly, which includes the incumbent), so the incumbent keeps propensity $0.2/5 + 0.8 = 0.84$ and each of the other four gets $0.2/5 = 0.04$, summing to 1. That table is what the log stores for the slot. In this particular run the random number drawn for the exploration test (last line of the output) was 0.086, below 0.2, so exploration did fire; the uniform pick among the five candidates happened to land on the incumbent trail running vest pack, so the page came out unchanged. The propensity table describes the probabilities, which are the same whichever item the draw picks.

The added lines print how the scores arise: each item's score is 2.0 times its lexical cosine, plus 1.5 times its embedding dot product with the user, plus 0.3 times its scaled log popularity. The belt beats the road shoes because its embedding feature is much larger (0.995 against 0.291), and 1.5 times that gap outweighs the road shoes' lead on the lexical and popularity features. The two pairwise-loss lines show the loss is smaller (0.450) when the clicked item already scores higher and larger (0.834) when the model ranked a skipped item above the clicked one.

Trade-offs and what would change the design

Pitfalls

• Comparing raw lexical and embedding scores as if they shared a scale; use source indicators or calibrate.
• Evaluating the reranker only offline on logged clicks without correcting for position and exposure bias.
• Exploration without logged propensities: the data are then unusable for unbiased training.
• Letting exploration touch the first slot or sensitive content.

Direct answer

Approximate nearest neighbor (ANN) search finds vectors that are very likely among the closest to a query vector, without comparing the query to every stored vector. An embedding-based recommender needs it because retrieval is "find the items whose embedding has the largest dot product (or smallest distance) with this user's embedding", and doing that exactly means one score per catalogue item per request. With millions of items that is too much work for a request-time budget. What you give up is a guarantee: some true top-k items are occasionally missed (lower recall), and the index adds build time, memory, and awkward updates.

What is being searched

Two-tower retrieval produces one vector per item (offline) and one vector per user request (online). The task is top-$k$ by similarity. Exact search computes $n$ similarities of dimension $d$ per query, so the cost is $O(n d)$ per query. ANN indexes cut the number of vectors touched, trading accuracy for work.

Two common index families

• Inverted file (IVF): cluster the item vectors (for example with k-means, which repeatedly assigns each vector to its nearest centre point and moves each centre to the mean of its members) into buckets; at query time find the closest few bucket centres and scan only those buckets. The knob is nprobe, the number of buckets scanned.
• Graph indexes (for example HNSW, a layered neighbour graph): link each vector to nearby vectors and walk the graph greedily towards the query. Layered means a few sparse upper layers with long links let the search jump across the space, then a dense bottom layer refines locally. The two knobs are usually called M, the number of links per node, and ef, the width of the search frontier (how many best-so-far candidates the walk keeps).

A tiny graph shows the walk and why it is approximate. Eight points in 2-D, each linked to its two nearest points; the walk starts at point 0 and repeatedly moves to whichever linked point is closest to the query, stopping when no neighbour is closer. A frontier of width 1 is that plain greedy walk; a wider frontier keeps several candidates alive:

import numpy as np

# Eight 2-D points, each linked to its two nearest points. A greedy walk moves to whichever linked point is closest to the query.
pts = np.array([[0.0, 0.0], [1.0, 0.2], [2.0, 0.1], [3.0, 0.3], [4.0, 0.0], [1.5, 1.5], [2.5, 1.6], [3.5, 1.4]])
dist = np.linalg.norm(pts[:, None] - pts[None], axis=2)
np.fill_diagonal(dist, np.inf)
links = {i: sorted(np.argsort(dist[i])[:2].tolist()) for i in range(len(pts))}
print("links:", links)

query = np.array([3.6, 1.3])
dq = lambda i: float(np.linalg.norm(pts[i] - query))
node, path, evaluated = 0, [0], {0}
while True:
    evaluated.update(links[node])
    best = min(links[node] + [node], key=dq)
    if best == node:
        break
    node = best
    path.append(node)
print("walk:", path, "distances:", [round(dq(i), 2) for i in path])
print("points compared with the query:", len(evaluated), "of", len(pts))
nearest = int(np.argmin([dq(i) for i in range(len(pts))]))
print("exact nearest point:", nearest, "at distance", round(dq(nearest), 2))

def beam_walk(width):
    """Keep the `width` closest points found so far and keep expanding until none of them has an unexplored link."""
    beam, seen, compared = [0], {0}, {0}
    while True:
        new = [j for i in beam for j in links[i] if j not in seen]
        if not new:
            return sorted(beam, key=dq)[0], len(compared)
        seen.update(new); compared.update(new)
        beam = sorted(set(beam) | set(new), key=dq)[:width]

for width in (1, 2, 3):
    best, n = beam_walk(width)
    print(f"frontier width {width}: returns point {best}, compared {n} of {len(pts)} points")

Output:

links: {0: [1, 2], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3, 7], 5: [1, 6], 6: [5, 7], 7: [3, 6]}
walk: [0, 2, 3] distances: [3.83, 2.0, 1.17]
points compared with the query: 5 of 8
exact nearest point: 7 at distance 0.14
frontier width 1: returns point 3, compared 5 of 8 points
frontier width 2: returns point 7, compared 8 of 8 points
frontier width 3: returns point 7, compared 8 of 8 points

Reading it: the greedy walk goes 0, 2, 3 and stops at point 3 (distance 1.17) after comparing 5 of the 8 points, because none of point 3's links is closer to the query, yet point 7 (distance 0.14) is the true nearest. That is a miss caused by a locally best but globally wrong stopping point. A frontier of width 2 keeps point 7's route alive and returns it, here at the price of comparing all 8 points; on this tiny graph that is no saving, but on millions of points the walk still touches only a small fraction. This is the trade the ef knob controls: a wider frontier raises recall and costs more comparisons.

Both are approximate: a true neighbour sitting in an unscanned bucket, or behind a bad greedy step in the graph, is missed. Compression (such as product quantisation, which cuts each vector into pieces and replaces each piece by the number of its nearest entry in a small learned table, so a vector of many floats is stored as a few small codes) further trades accuracy for memory.

Worked example: the recall versus work trade-off

The program builds 20,000 synthetic item vectors in 32 dimensions that fall into 50 topic groups, 200 queries from the same distribution, a 64-bucket IVF index from scikit-learn k-means, and measures recall@10 (the fraction of the exact top 10 that the ANN search returns) against how many items were scanned. Work is counted in items scanned, not seconds. The 64 bucket-centre comparisons per query are not included in the scanned fraction.

import numpy as np
from sklearn.cluster import KMeans

rng = np.random.default_rng(0)
n_items, dim, n_topics, n_lists, k = 20000, 32, 50, 64, 10
topics = rng.normal(size=(n_topics, dim))
items = topics[rng.integers(n_topics, size=n_items)] + 0.6 * rng.normal(size=(n_items, dim))
queries = topics[rng.integers(n_topics, size=200)] + 0.6 * rng.normal(size=(200, dim))

# Exact search: score every item for every query, keep the top k by dot product.
exact = np.argsort(-(queries @ items.T), axis=1)[:, :k]

# IVF-style index: k-means splits the items into n_lists buckets; a query scans only its nprobe nearest buckets.
km = KMeans(n_clusters=n_lists, n_init=1, random_state=0).fit(items)
buckets = [np.where(km.labels_ == c)[0] for c in range(n_lists)]


def ann_search(q, nprobe):
    near = np.argsort(((km.cluster_centers_ - q) ** 2).sum(1))[:nprobe]
    cand = np.concatenate([buckets[c] for c in near])
    top = cand[np.argsort(-(items[cand] @ q))[:k]]
    return top, len(cand)


print("nprobe  recall@10  items_scanned_fraction")
for nprobe in [1, 2, 4, 8, 16, 64]:
    hits, scanned = 0, 0
    for q, truth in zip(queries, exact):
        top, n_cand = ann_search(q, nprobe)
        hits += len(set(top) & set(truth))
        scanned += n_cand
    recall = hits / (k * len(queries))
    frac = scanned / (len(queries) * n_items)
    print(f"{nprobe:6d}  {recall:9.3f}  {frac:22.3f}")
    if nprobe == n_lists:
        assert recall == 1.0 and frac == 1.0   # scanning every bucket is exact search
print("nprobe=64 reproduces exact search: True")

Output:

nprobe  recall@10  items_scanned_fraction
     1      0.884                   0.017
     2      0.989                   0.033
     4      0.994                   0.066
     8      0.995                   0.132
    16      1.000                   0.260
    64      1.000                   1.000
nprobe=64 reproduces exact search: True

Reading it: scanning one bucket looks at 1.7% of the catalogue and recovers 88.4% of the true top 10. Four buckets look at 6.6% and reach 99.4%. Scanning all 64 buckets is exact search by construction (the assert confirms recall 1.0 and fraction 1.0), and it is the right sanity check for any ANN code you write. This data is strongly clustered, which flatters IVF; on data without cluster structure the same nprobe gives lower recall, so you always measure recall on your own vectors against an exact baseline.

Case: 50 million item vectors with live inserts

Take 50 million items with 128-dimensional vectors, and assume 5% of the catalogue changes every hour (new and updated items). The arithmetic below uses stated assumptions; replace each with a number from your own system.

n, dim, M = 50_000_000, 128, 16          # items, vector width, graph links per node
GB = 1e9
print(f"float32 vectors  {n * dim * 4 / GB:6.1f} GB")
print(f"float16 vectors  {n * dim * 2 / GB:6.1f} GB")
print(f"graph links      {n * 2 * M * 4 / GB:6.1f} GB  (up to 2*M neighbour ids of 4 bytes at the bottom layer)")
print(f"32-byte PQ codes {n * 32 / GB:6.1f} GB  (one byte per piece, 32 pieces per vector)")

per_hour = int(n * 0.05)
per_second = per_hour / 3600
print(f"inserts: {per_hour:,} per hour = {per_second:,.0f} per second")

# Assumption: one graph search compares about 2,000 stored vectors with the query.
graph_query = 2_000 * dim
print(f"multiply-adds per query: graph search {graph_query:,} vs exact scan of everything {n * dim:,}")
for fold_seconds in (600, 60, 10):
    buffer = int(per_second * fold_seconds)
    scan = buffer * dim
    print(f"fold every {fold_seconds:3d} s: buffer {buffer:>7,} vectors, scan {scan:>11,} multiply-adds "
          f"= {scan / graph_query:5.1f}x a graph query, {scan / (n * dim):.2%} of an exact scan")

Output:

float32 vectors    25.6 GB
float16 vectors    12.8 GB
graph links         6.4 GB  (up to 2*M neighbour ids of 4 bytes at the bottom layer)
32-byte PQ codes    1.6 GB  (one byte per piece, 32 pieces per vector)
inserts: 2,500,000 per hour = 694 per second
multiply-adds per query: graph search 256,000 vs exact scan of everything 6,400,000,000
fold every 600 s: buffer 416,666 vectors, scan  53,333,248 multiply-adds = 208.3x a graph query, 0.83% of an exact scan
fold every  60 s: buffer  41,666 vectors, scan   5,333,248 multiply-adds =  20.8x a graph query, 0.08% of an exact scan
fold every  10 s: buffer   6,944 vectors, scan     888,832 multiply-adds =   3.5x a graph query, 0.01% of an exact scan

Choosing the primary index: the graph index (HNSW style) is the primary, because it accepts new vectors one at a time without retraining anything, and at about 19 GB for float16 vectors plus links the whole thing can sit in RAM, split across a few shards. A clustering index (IVF) also accepts inserts, since a new vector just joins its nearest bucket, but its buckets were fitted to yesterday's data, so recall slowly decays as the data shifts and the clusters need periodic refitting.

Absorbing the 694 inserts per second: do not write each one straight into the big graph on the query path, because insertion is itself a search and competes with queries for the same cores. Put new vectors into a small exact-scan buffer that every query also scans, merge its results with the main index, and fold the buffer into the graph in batches off the query path. Judge the buffer against the graph search it runs beside, not against an exact scan of everything. Taking an assumed 2,000 vector comparisons per graph search, folding every 10 minutes leaves a buffer whose scan costs about 200 times a graph query (under 1% of an exact scan, yet far more than the main search), folding every minute still leaves about 21 times, and folding every 10 seconds brings it to about 3.5 times. So fold every few seconds to tens of seconds, not every few minutes. Deletes are the weak spot: many graph implementations only mark a node as deleted, so the graph keeps dead nodes and its quality drifts until a periodic rebuild from a clean snapshot, swapped in atomically.

The fallback when requirements tighten or inserts spike:

• Recall requirement tightens: first widen the search frontier ef (more comparisons, more latency). If that is not enough, rebuild with more links per node, which costs memory (the links row above grows in proportion to M). Another route is to search compressed codes cheaply, then re-score the top few hundred candidates with the full float vectors, which lifts accuracy at the price of one extra fetch.
• Memory becomes the limit: switch the stored vectors to PQ codes (1.6 GB against 12.8 GB above), accepting the accuracy loss, and recover part of it with the re-scoring step.
• Inserts spike beyond what the fold keeps up with: the buffer grows, every query pays for scanning it, so cap its size, fold more often, and if it still grows, keep serving from the main index and let the newest items wait for the next fold (stale but correct beats slow).

Whatever the choice, measure recall against an exact baseline on a sample of queries after each fold and each rebuild, because the numbers above are sizing arithmetic and say nothing about recall.

What you give up, listed

1. Recall: some true neighbours are missed; the loss is tunable but never exactly zero below full scan.
2. Predictable correctness: results are not guaranteed to match exact search, so tests compare to an exact baseline sample.
3. Index maintenance: inserts and deletes are cheaper in some indexes than others, and clustering-based indexes drift if the data distribution moves and need periodic rebuilds.
4. Memory: graph links add storage on top of the vectors.
5. A hard similarity shape: indexes are built for one similarity (dot product, cosine, or L2, the straight-line Euclidean distance). Cosine equals the dot product only for unit-length vectors (vectors divided by their length so the length is 1), so normalise first if the index uses cosine.

When exact search is fine

For a catalogue of tens of thousands of items, a matrix multiply on one machine is simple and exact. Reach for ANN when the per-request exact scan no longer fits the latency budget.

Common mistakes

• Reporting ANN quality as "latency" without recall, or recall without the exact baseline it was measured against.
• Using the metric the index was not built for (dot-product scores over an L2 index).
• Forgetting that the retrieval stage only has to put good items in the candidate set; a later ranker reorders them, so recall of the relevant items at the retrieval depth is what matters, not exact order.

The idea in plain words

An embedding is a list of numbers (a vector) that places an item or user in space so that similar things land close together. Brute-force top-k retrieval means: score the user against every item, then keep the k best. Cosine similarity compares directions and ignores length:

Here $u \cdot v$ is the dot product (sum of element-wise products) and $\lVert u \rVert$ is the vector's length (its L2 norm, the straight-line length $\sqrt{\sum_k u_k^2}$). Cosine equals the plain dot product when the two lengths multiply to 1 (in particular when both vectors have length 1), so you either normalize first or divide by the lengths while scoring.

Implementation

The steps with shapes, for $N$ items of dimension $d$:

1. items is an $(N, d)$ matrix and user a $(d,)$ vector.
2. items @ user gives $N$ dot products in one pass: $2Nd$ floating-point operations.
3. Divide by the item norms (shape $(N,)$) times the user norm to get cosines.
4. Zero vectors (an item without an embedding) have no direction, so cosine is undefined. The code gives them a score of negative infinity so they are never returned, and raises an error if the user vector is zero.
5. np.partition finds the k-th best score in $O(N)$ without sorting everything. Every item scoring at least that value is kept, which includes every item tied with the k-th one, and only those few are sorted.
6. Scores are rounded to 6 decimals so float noise cannot reorder exact ties, and ties are broken by the lowest index, both inside the top k and at its edge (which of several tied items make the cut), so the output is the same on every run.
7. To recommend for a user id instead of an embedding you already hold, look up that user's row in the user-embedding table and pass it as user; the function is the same, only the source of the vector changes.

The driver builds 10,000 random item vectors, plants an item with no embedding (index 7) and an item (index 3) pointing in the same direction as item 100 but five times longer, and makes the user close to item 100. It checks the result against scikit-learn's cosine_similarity (with the zero row removed before the call, since the reference should not have to decide how to score it), shows that ranking by raw dot product gives a different list, and asks for the top 5 of 50 identical items to show that the lowest indices win a tie at the edge of the top k.

import numpy as np
from sklearn.metrics.pairwise import cosine_similarity

def top_k_cosine(user, items, k, eps=1e-12):
    """items: (N, d), user: (d,). Returns (indices, scores) of the k most similar items."""
    item_norm = np.linalg.norm(items, axis=1)              # (N,)
    user_norm = np.linalg.norm(user)                       # scalar
    if user_norm < eps:
        raise ValueError("zero user vector: cosine is undefined")
    dots = (items @ user).astype(np.float64)               # (N,)  one pass over the matrix
    scores = np.where(item_norm < eps, -np.inf, dots / np.maximum(item_norm * user_norm, eps))
    scores = np.round(scores, 6)                           # so float noise cannot reorder exact ties
    k = min(k, int((scores > -np.inf).sum()))
    if k < 1:
        return np.empty(0, dtype=np.int64), np.empty(0)
    kth = np.partition(scores, scores.size - k)[scores.size - k]   # k-th largest score, O(N)
    cand = np.flatnonzero(scores >= kth)                           # the k best plus anything tied with the k-th
    order = cand[np.lexsort((cand, -scores[cand]))][:k]            # score descending, then lowest index
    return order, scores[order]

rng = np.random.default_rng(0)
N, d, k = 10_000, 64, 5
items = rng.normal(size=(N, d)).astype(np.float32)
items[7] = 0.0                                             # an item with no embedding yet
items[3] = 5.0 * items[100]                                # same direction as item 100, 5x the length
user = items[100] + 0.1 * rng.normal(size=d).astype(np.float32)

idx, sc = top_k_cosine(user, items, k)
print("top-k idx   ", idx.tolist())
print("top-k scores", np.round(sc, 4).tolist())
print("norms of items 3 and 100:", round(float(np.linalg.norm(items[3])), 2), round(float(np.linalg.norm(items[100])), 2))

ref = cosine_similarity(user[None, :], np.delete(items, 7, axis=0))[0]   # sklearn, zero row removed
ref_idx = np.delete(np.arange(N), 7)[np.argsort(-ref)[:k]]
print("same index set as sklearn:", set(idx.tolist()) == set(ref_idx.tolist()),
      "| scores close:", bool(np.allclose(sc, np.sort(ref)[::-1][:k], atol=1e-5)))

dot_idx = np.argsort(-(items @ user))[:k]
print("raw dot-product top-k:", dot_idx.tolist(), "| same as cosine:", bool(np.array_equal(dot_idx, idx)))
try:
    top_k_cosine(np.zeros(d, dtype=np.float32), items, k)
except ValueError as e:
    print("zero user ->", e)
tied = np.tile(items[100], (50, 1))                        # 50 identical items: every score ties
print("50 identical items, k=5 ->", top_k_cosine(items[100], tied, 5)[0].tolist())

for n_items, dim in [(10_000, 64), (10_000_000, 128)]:
    gb = n_items * dim * 4 / 1e9
    gflop = 2 * n_items * dim / 1e9
    print(f"N={n_items:>10,} d={dim}: matrix {gb:9.4f} GB float32, {gflop:8.4f} GFLOP per query")

Output:

top-k idx    [3, 100, 7048, 9369, 7951]
top-k scores [0.9954, 0.9954, 0.4419, 0.4353, 0.4288]
norms of items 3 and 100: 38.04 7.61
same index set as sklearn: True | scores close: True
raw dot-product top-k: [3, 100, 1326, 9369, 7951] | same as cosine: False
zero user -> zero user vector: cosine is undefined
50 identical items, k=5 -> [0, 1, 2, 3, 4]
N=    10,000 d=64: matrix    0.0026 GB float32,   0.0013 GFLOP per query
N=10,000,000 d=128: matrix    5.1200 GB float32,   2.5600 GFLOP per query

Reading the output:

• Items 3 and 100 tie at the top with cosine 0.9954 despite norms of 38.04 and 7.61: cosine ignores length. The zero vector (index 7) never appears.
• The raw dot product returns [3, 100, 1326, 9369, 7951]; cosine returns [3, 100, 7048, 9369, 7951]. The third place differs because item 1326 has a long vector, and a dot product rewards length as well as direction. If your embeddings encode popularity in their length, a dot product ranks by popularity and direction together, which can be what you want, but it is a decision, not an accident.
• The check against scikit-learn prints that the index sets match and the scores agree to within 1e-5.
• With 50 identical items and k = 5, the result is the five lowest indices, 0 to 4, every run.

Complexity and when it stops being viable

• Time per query: $O(Nd)$ for the scoring pass plus $O(N)$ for the partition plus a final sort of the k best and any items tied with the k-th (usually about $k \log k$).
• Memory: the item matrix costs $N \cdot d \cdot 4$ bytes in float32. The last two printed lines compute it: 10,000 items at 64 dimensions is 0.0026 GB and 0.0013 GFLOP per query; 10,000,000 items at 128 dimensions is 5.1200 GB and 2.5600 GFLOP per query.
• Every query reads the entire matrix from memory. Each number fetched takes part in only about one multiply and one add, so the processor mostly waits for data to arrive: memory bandwidth (how many bytes per second memory can deliver) is the limit, not arithmetic. Batching many users into one matrix multiply lets each item row, once fetched, be used for every user in the batch, so one read of the matrix serves many queries (the reads are amortized over the batch). That is the first optimization.
• It stops being viable when the catalog no longer fits in one machine's memory, or when queries per second times the per-query cost exceeds the hardware, or when the latency budget (tens of milliseconds for a recommendation request) cannot afford a full scan. Then move to an approximate nearest-neighbour (ANN) index such as an inverted file (IVF, which groups vectors into clusters and scans only the nearest clusters) or HNSW (a navigable graph of neighbours). These trade a little recall for far fewer comparisons, so you must measure their recall against this exact brute-force baseline, which is the reason to keep the exact function around.

Edge cases and pitfalls

• Zero vectors and a zero user vector (handled above).
• Fewer than k valid items (the code clamps k, and returns empty arrays if no item is valid).
• Normalizing once offline and storing unit vectors makes cosine a plain dot product at query time and saves the norm division.
• float16 or int8 storage cuts memory but changes scores slightly; re-check recall.
• Ties and near-ties make results order-dependent unless you break them explicitly. A partition alone does not do it: it may keep any of the items tied at the k-th score, so the tied items are gathered and ordered by index, as the code does.

Recommendation

Use a bi-encoder (two-tower model) to retrieve a shortlist from the whole catalogue, and a cross-encoder to re-rank only that shortlist, when the top of the list must be precise and the shortlist is small enough for the latency budget. Skip the cross-encoder when the page is already well served by the retrieval scores, when the latency or compute budget cannot afford one forward pass per candidate, or when there is no joint query-item signal for it to exploit.

The two architectures

Two words used below: a forward pass is one run of an input through the network to get its output, and attention is the mechanism by which each token (word piece) in the input mixes in information from the other tokens, with weights the network learns.

• Bi-encoder / two-tower. One network turns the query (or user) into a vector, another turns the item into a vector, and relevance is a dot product or cosine similarity of the two. Item vectors do not depend on the query, so they are computed ONCE, offline, and stored in an ANN (approximate nearest neighbour) index. Serving cost is one query encoding plus an index lookup, and an approximate index lookup grows only slowly with catalogue size (roughly logarithmically for graph indexes), instead of needing one forward pass per item.
• Cross-encoder. One network reads the query and the item TOGETHER (for text, both token sequences in one input with attention across them) and outputs a relevance score. It can model fine-grained interactions: a negation, a matching number, a user feature meeting a specific item attribute. For example, for the query "laptop without touchscreen" and the item "laptop with touchscreen display", reading both together lets the model connect "without" in the query to "touchscreen" in the item and see a mismatch, whereas two separately made vectors both mostly say "laptop, touchscreen" and land close together; the word-count example further below shows that failure with a word-count stand-in. Nothing about the pair can be pre-computed, so the cost is one forward pass per candidate.

Why not use the cross-encoder everywhere

At an assumed 5 ms per pair (an assumption for illustration), 100 pairs take 0.5 s one by one and 1,000,000 pairs take 5,000 s, per query. Batching and parallel hardware cut that, but the cost still grows linearly in the number of candidates and in traffic. That is the reason for two stages.

When a cross-encoder re-ranker pays off

1. Precision at the top matters most (a handful of results are shown, or an LLM reads only the first few passages).
2. Fine-grained interaction decides relevance and the bi-encoder's single-vector compression loses it (long queries, exact attributes, negations).
3. The shortlist is small (tens to a few hundred) and the latency budget covers it.
4. You have labelled pairs or a strong teacher to train it; it needs query-item training data, ideally with hard negatives from the first stage.

Hybrid designs

The first design is the one to know and defend; the other four are refinements you reach for when it falls short.

• Retrieve then re-rank, the standard cascade: a bi-encoder (often fused with BM25, a classic keyword score that rewards query words that appear often in a document, are rare across the collection, and are not diluted by a long document) gives K candidates, and the cross-encoder orders them. Fusing two ranked lists is commonly done with reciprocal rank fusion: each document earns $1/(c+\text{rank})$ from every list it appears in, where rank is its position in that list (1 for the best) and $c$ is a constant that softens the gap between the top positions (60 is a common choice), and the document's fused score is the sum. The fusion example further below does one by hand.
• Distillation: train the bi-encoder (the student) to imitate the cross-encoder's scores (the teacher), getting some of its quality at retrieval cost.
• Hard negatives: a hard negative is an item that looks relevant to the model but is not; use the cross-encoder to find the items the bi-encoder ranks high that are not relevant, then retrain the bi-encoder on them, since easy negatives teach it little.
• Late interaction: keep one vector per token and compare them at query time, so some interaction is possible with pre-computed item data; it sits between the two on cost and quality.
• Caching and gating: cache scores for frequent queries, and run the cross-encoder only when the first stage is uncertain (a small margin, meaning a small gap between the top candidates' scores).

Computed example: how big should the shortlist be

The program below uses noisy-score stand-ins, not real encoders: each model's score is the true relevance plus Gaussian noise, with the bi-encoder noisier (standard deviation 1.0) than the cross-encoder (0.3). The noise levels are assumptions. 5000 items, 300 seeds. "Overlap" is the share of the true top-10 items found in the returned top 10: an overlap of 0.18 means about 2 of the 10 returned items belong to the true best 10, so it reads like precision at 10 against the ground truth.

import numpy as np

# Stand-ins: each "model" is the item's true relevance plus Gaussian noise. The bi-encoder is noisier
# (it compresses query and item into separate vectors); the cross-encoder is less noisy but costs one
# forward pass per (query, item) pair. These are not real encoders; the noise levels are assumptions.
N, SEEDS, SD_BI, SD_CROSS, TOPN = 5000, 300, 1.0, 0.3, 10
rng = np.random.default_rng(0)

def overlap_at_10(ranked_idx, truth):          # share of the true top-10 present in the first 10 returned
    return len(set(ranked_idx[:TOPN]) & set(truth)) / TOPN

Ks = (10, 50, 200, 1000, 5000)
res = {K: [] for K in Ks}; bi_only = []; recall_in_K = {K: [] for K in Ks}
for _ in range(SEEDS):
    true = rng.normal(size=N)
    truth = np.argsort(-true)[:TOPN]
    bi = true + SD_BI * rng.normal(size=N)
    cross = true + SD_CROSS * rng.normal(size=N)
    bi_rank = np.argsort(-bi)
    bi_only.append(overlap_at_10(bi_rank, truth))
    for K in Ks:
        cand = bi_rank[:K]                                  # stage 1: bi-encoder shortlist
        recall_in_K[K].append(len(set(cand) & set(truth)) / TOPN)
        final = cand[np.argsort(-cross[cand])]              # stage 2: cross-encoder reranks the shortlist
        res[K].append(overlap_at_10(final, truth))

print(f"bi-encoder alone, top-10 overlap with true top-10: {np.mean(bi_only):.2f}")
print(f"{'K shortlisted':>14}{'true top-10 inside shortlist':>30}{'final top-10 overlap':>24}{'cross-encoder calls/query':>28}")
for K in Ks:
    print(f"{K:>14}{np.mean(recall_in_K[K]):>30.2f}{np.mean(res[K]):>24.2f}{K:>28}")

# Cost arithmetic with ASSUMED per-pair cost: 5 ms per cross-encoder pair on one accelerator slot
cost_ms = 5
print()
print(f"assumed cross-encoder cost per pair: {cost_ms} ms")
for n in (100, 1_000_000):
    print(f"scoring {n:>9,} pairs one by one: {n * cost_ms / 1000:>10,.1f} s")

Output:

bi-encoder alone, top-10 overlap with true top-10: 0.18
 K shortlisted  true top-10 inside shortlist    final top-10 overlap   cross-encoder calls/query
            10                          0.18                    0.18                          10
            50                          0.43                    0.41                          50
           200                          0.74                    0.58                         200
          1000                          0.97                    0.64                        1000
          5000                          1.00                    0.64                        5000

assumed cross-encoder cost per pair: 5 ms
scoring       100 pairs one by one:        0.5 s
scoring 1,000,000 pairs one by one:    5,000.0 s

What it shows, about the cascade's structure rather than any specific model:

• The bi-encoder alone finds 0.18 of the true top-10 in its top 10 (about 2 of 10).
• Re-ranking helps only once the shortlist contains the right items: with K = 10 the re-rank cannot change anything (0.18), with K = 50 it is slightly lower (0.41) than the share contained (0.43), and with K = 200 the shortlist holds 0.74 and the final overlap is 0.58.
• The curve flattens: from K = 1000 to K = 5000 recall inside the shortlist goes from 0.97 to 1.00 but the final overlap stays at 0.64, the cross-encoder's own ceiling in this setup, while its calls grow 5x. So pick K at the knee, where retrieval recall is high and extra calls stop buying quality.

Two small computed examples: fusing two lists, and a query a bag of words gets wrong

The first part fuses two ranked lists by hand-sized reciprocal rank fusion with $c=60$. The second uses a word-count vector as a stand-in for "one vector per side, made without seeing the other side" (it is a stand-in, not a real bi-encoder, which does capture some word order); it shows how such a summary scores a negated query.

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.metrics.pairwise import cosine_similarity

# Reciprocal rank fusion of two ranked lists (best first). c = 60 is an assumed, commonly used constant.
c = 60
lists = {"vector search": ["d1", "d2", "d3", "d4"], "keyword (BM25) search": ["d3", "d1", "d5", "d2"]}
fused = {}
for name, docs in lists.items():
    for rank, doc in enumerate(docs, start=1):
        fused[doc] = fused.get(doc, 0.0) + 1 / (c + rank)
for doc, s in sorted(fused.items(), key=lambda kv: -kv[1]):
    where = {n: l.index(doc) + 1 for n, l in lists.items() if doc in l}
    print(f"{doc}: fused score {s:.5f}   ranks {where}")

# Stand-in for separately made vectors: word counts, one vector per text.
query = "laptop without touchscreen"
items = ["laptop with touchscreen display", "laptop with matte display"]
vec = CountVectorizer().fit([query] + items)
sims = cosine_similarity(vec.transform([query]), vec.transform(items))[0]
print()
for item, s in zip(items, sims):
    print(f"similarity of the query to '{item}': {s:.3f}")

Output:

d1: fused score 0.03252   ranks {'vector search': 1, 'keyword (BM25) search': 2}
d3: fused score 0.03227   ranks {'vector search': 3, 'keyword (BM25) search': 1}
d2: fused score 0.03175   ranks {'vector search': 2, 'keyword (BM25) search': 4}
d5: fused score 0.01587   ranks {'keyword (BM25) search': 3}
d4: fused score 0.01562   ranks {'vector search': 4}

similarity of the query to 'laptop with touchscreen display': 0.577
similarity of the query to 'laptop with matte display': 0.289

In the fusion, d1, d2 and d3 appear in both lists, d1 and d3 sit near the top of both and finish first (d1: 1/61 + 1/62 = 0.03252; d3: 1/63 + 1/61 = 0.03227), while d4 and d5 appear in one list only and finish last; no score from either list had to be on a comparable scale, because only ranks are used. In the second part the touchscreen laptop, the wrong answer, scores 0.577 against 0.289 for the matte-display laptop, because counting words cannot represent "without". A cross-encoder reads the query and the item together, which is how it can catch this case; an encoder that makes one vector per side can also miss it, which is why precision at the top often needs the second stage.

What would flip the choice

If the cross-encoder cannot hit the latency budget even for 50 candidates, use a smaller or distilled model, or late interaction. If the first stage's recall at the shortlist size is poor, improve it (better negatives, hybrid lexical retrieval) before spending on the re-ranker; a re-ranker cannot recover an item that was never retrieved.

Common mistakes

• Evaluating the re-ranker on a pre-filtered easy candidate set instead of what the first stage actually returns.
• Fixing quality problems in stage 2 that are recall problems in stage 1.
• Quoting a cross-encoder's gain without its latency and cost per query.