TL;DR — A search system turns a query into a ranked list of documents in tens of milliseconds over billions of docs. The production shape is a funnel: retrieval (cheap, high-recall — an inverted index with BM25 for lexical, plus vector/ANN search over embeddings for semantic) → pre-ranking (a light model trims to hundreds) → ranking (a heavy learning-to-rank model like LambdaMART or a cross-encoder) → re-ranking (diversity, business rules, freshness). Hybrid search (lexical + semantic, fused) is now the default because BM25 nails exact terms/rare words and vectors nail meaning/synonyms. Core math to know cold: BM25, NDCG, and the three LTR loss families (pointwise/pairwise/listwise).
1. Simple explanation
Search answers: "Given this query, which documents are most relevant, in what order?" — fast, over a huge corpus.
Analogy — a library with a genius index card system. The inverted index is the card catalog: for every word, a card lists exactly which books contain it, so you never scan every book. BM25 is the librarian's rule of thumb for how relevant a book is: it counts how often your words appear, but discounts words that appear everywhere ("the") and doesn't over-reward a 900-page book just for being long. But a catalog only matches words — if you ask for "laptop" it misses a book about "notebook computers." Semantic search (embeddings) is a second librarian who understands meaning, catching synonyms and intent. Hybrid search asks both and merges their answers. Finally a ranking model (learning-to-rank) does the fine sorting, having learned from millions of past clicks what "relevant" really looks like.
2. Diagram
SEARCH RANKING FUNNEL (billions of docs → 10 results, ~50ms)
query: "cheap noise cancelling headphones"
│
▼
┌──────────────────────┐ QUERY UNDERSTANDING
│ query understanding │ tokenize · spell-correct ("headfones"→"headphones")
│ │ synonyms/expansion (cheap→budget) · intent · entities
└──────────┬───────────┘
▼
┌───────────────────────────────────────────────┐ RETRIEVAL (high recall, cheap)
│ LEXICAL: inverted index + BM25 ─┐ │ • exact terms, rare words, IDs
│ ├─► fuse ──►│ • ANN over embeddings (HNSW/IVF)
│ SEMANTIC: query embedding + ANN ─┘ (RRF) │ • ~thousands of candidates
└───────────────────────┬───────────────────────┘
▼
┌──────────────────────┐ PRE-RANKING (light model) → hundreds
├──────────────────────┤
│ RANKING (heavy) │ Learning-to-Rank: LambdaMART / cross-encoder
│ │ rich features (BM25 score, freshness, clicks, embedding sim)
└──────────┬───────────┘
▼
┌──────────────────────┐ RE-RANKING: diversity, dedup, freshness,
│ re-ranking + rules │ business boosts (ads/inventory), personalization
└──────────┬───────────┘
▼
10 blue links ──► log clicks/dwell/skips ──► train the LTR model
3. How it works (the system-design flow)
3.1 Requirements
Functional: query in → ranked, relevant documents out; support typos, synonyms, filters/facets.
Non-functional:
| Constraint | Typical target |
|---|---|
| Latency | p99 ≤ ~100–200 ms end-to-end |
| Scale | 10⁹–10¹² docs, high QPS, corpus updates continuously |
| Freshness | new/updated docs searchable within seconds–minutes |
| Relevance | measured by NDCG / MRR + online CTR |
3.2 Query understanding
Before retrieval, normalize and enrich the query — cheap wins in relevance:
- Tokenization / normalization: lowercase, stemming/lemmatization ("running"→"run"), stop-word handling.
- Spell correction: edit-distance + a language model ("headfones"→"headphones").
- Synonyms / query expansion: "cheap"→{budget, affordable}; domain thesauri or learned expansions.
- Intent & entity detection: navigational vs. informational vs. transactional; recognize brands, categories → route to filters/verticals.
3.3 Retrieval — lexical (inverted index + BM25)
The inverted index maps each term → posting list of doc IDs (+ term frequencies/positions). To answer a query you intersect/union a few short posting lists instead of scanning the corpus — this is what makes search fast.
BM25 scores each candidate doc for the query (see §4.1). It's a 30-year-old bag-of-words function that still powers Elasticsearch/OpenSearch/Lucene, with zero training — a shockingly strong baseline and a must-know.
3.4 Retrieval — semantic (embeddings + ANN)
Lexical fails on vocabulary mismatch ("laptop" vs "notebook"). Dense retrieval encodes query and docs into vectors (via a bi-encoder / two-tower model trained with contrastive learning) so meaning is close in vector space. At query time, embed the query and do approximate nearest neighbor (ANN) search — HNSW, IVF-PQ, ScaNN/FAISS — because exact nearest-neighbor over billions of vectors is too slow.
3.5 Hybrid search (lexical + semantic)
Neither alone is enough: BM25 wins on exact/rare terms, IDs, and out-of-domain queries; dense wins on synonyms/paraphrase/intent. Hybrid runs both and fuses the lists — most robustly with Reciprocal Rank Fusion (RRF) (rank-based, no score-scale calibration needed) or a weighted score blend. This is the current production default and a very common interview topic (and the retrieval backbone of RAG).
3.6 Ranking — learning-to-rank (LTR)
Retrieval gives a candidate set; a heavy LTR model does precision ranking using dozens–hundreds of features: BM25 score, embedding similarity, freshness, doc quality/PageRank, historical CTR, query-doc match features, personalization. Three loss families (see §4.3):
- Pointwise — predict an absolute relevance per doc (regression/classification), then sort. Simple; ignores that ranking is relative.
- Pairwise — learn "doc A > doc B" over pairs (RankNet, RankSVM). Models order directly.
- Listwise — optimize the whole list against a ranking metric (LambdaMART, ListNet, LambdaRank). LambdaMART (GBDT + lambda gradients that scale by the NDCG change from swapping a pair) is the classic strong baseline; increasingly a cross-encoder transformer re-ranks the top-k.
3.7 Serving
Sharded inverted index + sharded ANN index across machines; scatter-gather across shards, merge, then rank the merged top-k. Cache hot queries. Index updates via near-real-time segment writes. Keep the heavy ranker/cross-encoder only on the small top-k to fit latency.
3.8 Evaluation
- Offline: NDCG@k (graded relevance, position-discounted), MRR (first relevant result — good for navigational/QA), MAP, Precision/Recall@k. Uses human-labeled judgments or click-derived labels.
- Online: A/B test → CTR, click position/MRR, dwell/long-clicks, reformulation rate (bad = users re-typing), abandonment, conversion (e-commerce). Watch position bias in click labels.
4. The math
4.1 BM25 ★
The lexical relevance score of document D for query Q = {q₁…qₙ}:
BM25(D, Q) = Σ_i IDF(qᵢ) · ( f(qᵢ, D) · (k₁ + 1) )
─────────────────────────────────────────
f(qᵢ, D) + k₁ · ( 1 − b + b · |D| / avgdl )
f(qᵢ, D) = term frequency of qᵢ in D
|D| = length of D (in words) avgdl = average doc length in the corpus
k₁ ≈ 1.2–2.0 = term-frequency saturation (diminishing returns on repeats)
b ≈ 0.75 = length-normalization strength (0 = off, 1 = full)
IDF(qᵢ) = ln( 1 + (N − n(qᵢ) + 0.5) / (n(qᵢ) + 0.5) )
N = total docs n(qᵢ) = docs containing qᵢ
→ rare terms get HIGH idf (informative); common terms ("the") ~0.
Why the two knobs matter: k₁ makes the 10th occurrence of a word add far less than the 2nd (saturation — real relevance doesn't grow linearly). b stops long documents from winning just by being long (length normalization). This intuition is the #1 BM25 interview follow-up.
4.2 NDCG ★
DCG@k = Σ_{i=1..k} (2^rel_i − 1) / log2(i + 1) NDCG@k = DCG@k / IDCG@k
rel_i = graded relevance of the doc at rank i (e.g. 0–4 from human judges)
IDCG@k = DCG of the perfect ordering → normalizes to 0..1, comparable across queries
→ the log discount means a relevant doc at rank 1 is worth much more than at rank 10.
MRR (single relevant target): MRR = (1/|Q|) Σ_q 1/rank_of_first_relevant_q.
4.3 Learning-to-rank losses
POINTWISE (regression): L = Σ_d ( f(x_d) − rel_d )² → predict score, then sort
PAIRWISE (RankNet): for a pair where doc i should beat j,
P(i≻j) = σ( f(xᵢ) − f(xⱼ) ), L = − log P(i≻j) → learn the ORDER
LISTWISE (LambdaMART): gradient on pair (i,j) is scaled by the
|ΔNDCG| from swapping i and j: λ_ij = −σ(...) · |ΔNDCG_ij| → optimize the METRIC
LambdaMART = gradient-boosted trees driven by these lambda gradients; it's the canonical bridge from pairwise training to a listwise (NDCG) objective.
5. Real code
Minimal BM25 retrieval + hybrid fusion with a dense retriever, plus NDCG — the real production shape.
import math
from collections import Counter, defaultdict
class BM25:
def __init__(self, docs, k1=1.5, b=0.75):
self.k1, self.b, self.docs = k1, b, docs
self.N = len(docs)
self.tf = [Counter(d) for d in docs] # term freq per doc
self.len = [len(d) for d in docs]
self.avgdl = sum(self.len) / self.N
df = defaultdict(int) # doc freq per term
for tfd in self.tf:
for term in tfd: df[term] += 1
self.idf = {t: math.log(1 + (self.N - n + 0.5) / (n + 0.5)) for t, n in df.items()}
def score(self, query, i):
s = 0.0
for q in query:
if q not in self.tf[i]: continue
f = self.tf[i][q]
denom = f + self.k1 * (1 - self.b + self.b * self.len[i] / self.avgdl)
s += self.idf.get(q, 0.0) * (f * (self.k1 + 1)) / denom
return s
def search(self, query, top=10):
ranked = sorted(range(self.N), key=lambda i: self.score(query, i), reverse=True)
return ranked[:top]
# ---- HYBRID: fuse lexical (BM25) and semantic (dense) rankings via Reciprocal Rank Fusion
def reciprocal_rank_fusion(*ranked_lists, k=60):
scores = defaultdict(float)
for ranked in ranked_lists: # each is a list of doc ids
for rank, doc_id in enumerate(ranked):
scores[doc_id] += 1.0 / (k + rank + 1) # rank-based, scale-free
return [d for d, _ in sorted(scores.items(), key=lambda x: -x[1])]
# ---- NDCG@k for offline evaluation
def ndcg_at_k(ranked_ids, relevance, k=10):
def dcg(rels): return sum((2**r - 1) / math.log2(i + 2) for i, r in enumerate(rels))
gains = [relevance.get(d, 0) for d in ranked_ids[:k]]
ideal = sorted(relevance.values(), reverse=True)[:k]
return dcg(gains) / dcg(ideal) if dcg(ideal) > 0 else 0.0
# usage: hybrid = reciprocal_rank_fusion(bm25.search(q), dense_index.search(q_emb))
6. Real-world example
- Google Search — multi-stage: retrieval over an inverted index + neural retrieval, then learned ranking with hundreds of signals (relevance, quality, freshness, RankBrain/neural matching, BERT/MUM for query understanding), then re-ranking (diversity, spam demotion). Query understanding (spell, synonyms, entities via the Knowledge Graph) is a first-class stage.
- E-commerce search (Amazon, Instacart, Etsy) — relevance and business objectives (availability, margin, conversion, sponsored slots). BM25/lexical for exact SKU/attribute match + semantic for "gift for a runner"; LTR trained on purchases/clicks; heavy re-ranking for inventory and ads.
- Enterprise / RAG retrieval — hybrid BM25 + vector is the standard retriever feeding an LLM; RRF fusion + a cross-encoder re-rank of the top-k dramatically cuts hallucinations. This is the direct sibling of the vector retrieval in Recommendation Systems and of a domain (clinical) RAG system with a supervisor routing to specialist retrievers — same retrieval funnel, different consumer (LLM instead of a results page).
- Natural tie-in: the retrieval → rank → re-rank funnel here is the same two-stage architecture as Feed Ranking (candidate gen → ranking); search just swaps "engagement prediction" for "relevance," and BM25 gives you a strong training-free baseline that feeds is missing.
7. Interview questions companies actually ask
Q [easy] "What is an inverted index and why is it fast?"
A A map term → posting list of doc IDs (with tf/positions). Queries touch a few short lists
instead of scanning the corpus, turning O(corpus) into O(matching docs). Trades index
build/storage cost for query speed.
Q [easy] "What does BM25 do that plain term-frequency doesn't?"
A Two things: IDF down-weights common words; TF SATURATION (k1) gives diminishing returns on
repeated terms; and length normalization (b) stops long docs winning by size. A strong,
zero-training baseline still used in Elasticsearch/Lucene.
Q [medium] "Lexical (BM25) vs semantic (embedding) retrieval — when each?"
A BM25: exact terms, rare words, IDs/codes, out-of-domain, interpretable, no training.
Dense: synonyms, paraphrase, intent, cross-lingual — but needs a trained encoder + ANN and
can miss exact matches. Use HYBRID and fuse (RRF) to get both.
Q [medium] "Explain pointwise vs pairwise vs listwise learning-to-rank."
A Pointwise predicts an absolute relevance then sorts (ignores relativity). Pairwise learns
'A should beat B' over pairs (RankNet). Listwise optimizes the whole-list metric directly
(LambdaMART scales gradients by ΔNDCG of a swap) — usually best because NDCG is listwise.
Q [medium] "Which metric would you optimize and report — and why not accuracy?"
A NDCG@k for graded relevance (position-discounted), MRR for navigational/QA (first hit).
Accuracy ignores ORDER, which is the whole point of search. Validate offline NDCG gains
with an online A/B on CTR/long-clicks/reformulation rate.
Q [hard] "Design search for an e-commerce site (10^8 products)."
A Query understanding (spell/synonym/attribute parse) → hybrid retrieval (lexical for SKU/
attributes + dense for intent) → LTR trained on clicks/purchases with business features →
re-rank for availability, diversity, sponsored slots. Shard index+ANN; cache; NDCG offline
+ conversion A/B online. Handle cold-start products with content features.
Q [hard] "How do you fuse lexical and semantic results with different score scales?"
A Don't add raw scores (incomparable scales). Use Reciprocal Rank Fusion (score = Σ 1/(k+rank))
which is rank-based and scale-free, or min-max/z-normalize per source then weight, or train
a ranker that takes both scores as features.
Q [hard] "Your click logs are biased toward top results. How do you train fairly?"
A Position bias: high ranks get more clicks regardless of relevance. Correct with
inverse-propensity weighting (estimate examination probability per position), add
interleaving/randomization to gather unbiased data, and include position as a de-biasing
feature. Prefer graded human judgments where feasible.
Q [hard] "How would you add typo tolerance and synonyms without killing latency?"
A Offline: build a spell model (edit-distance + LM) and synonym/expansion dictionaries or
learned expansions applied at query time (cheap). Index fuzzy variants (n-grams) selectively.
Route rewrites into the same retrieval; cap expansion breadth to protect the latency budget.
Sources: ML System Design: Build a Search Ranking System — techinterview · What is BM25 — GeeksforGeeks · Learning to Rank in Web Search · Loss Functions of Rankers: Pairwise vs Listwise · XGBoost Learning to Rank docs · Hybrid Retrieval with BM25 + vectors
8. When to use / tradeoffs
BM25 / lexical only → small corpora, exact-match domains (code/legal/IDs), no training data,
need interpretability. Weak on synonyms/intent.
Dense / semantic only→ strong on meaning & paraphrase, but needs a trained encoder + ANN infra
and can miss exact/rare terms; embeddings drift → re-index cost.
HYBRID (fused) → the production default; best recall, more infra + a fusion knob to tune.
Heavy LTR / cross-encoder → big relevance gains on top-k, but latency-costly → only on the
small re-rank set, never the full corpus.
Query understanding → cheap, high-ROI relevance (spell/synonym/intent) — almost always worth it.
9. Summary + related articles
- Search is a funnel: query understanding → retrieval (inverted index + BM25, and ANN over embeddings) → pre-rank → LTR ranking → re-rank.
- BM25 = IDF × saturated, length-normalized term frequency (know k₁ and b). Hybrid fuses lexical + semantic (RRF) and is the modern default (and the RAG retriever).
- Learning-to-rank comes in pointwise / pairwise / listwise; LambdaMART optimizes NDCG via lambda gradients.
- Evaluate with NDCG@k / MRR offline + CTR/long-clicks/reformulation A/B online; beware position bias.
Related: Recommendation Systems · Feed Ranking · Fraud Detection · ML Inference Systems · Common ML System Design Interview Questions · (embeddings/RAG: ../../nlp/3-6/)
Resources
- BM25 / Okapi (Robertson & Zaragoza) — https://www.staff.city.ac.uk/~sbrp622/papers/foundations_bm25_review.pdf
- Learning to Rank overview — https://en.wikipedia.org/wiki/Learning_to_rank
- Elasticsearch relevance / BM25 — https://www.elastic.co/guide/en/elasticsearch/reference/current/index-modules-similarity.html
- Dense Passage Retrieval (Karpukhin et al.) — https://arxiv.org/abs/2004.04906