Semantic Search & Embeddings
Bi-encoder vs cross-encoder, ANN indexes: HNSW / IVF
Keyword search breaks the moment the user's words don't match the document's. "heart attack symptoms" misses a page that says "myocardial infarction presentation" — same meaning, zero shared tokens, and BM25 has no idea. Semantic search maps queries and documents into an embedding space where *meaning* decides similarity.
Solving vocabulary creates a scale problem. The most accurate comparison is a cross-encoder — feed query and document in together so the model weighs every interaction. But it reruns per query-document pair, so it can't exceed a few hundred documents per query. Useless over 50M docs. The bi-encoder (two-tower) encodes each side separately: slightly less precise, but document embeddings are query-independent, so precompute them offline and retrieve with ANN (Approximate Nearest Neighbor) over billions in milliseconds.
Production uses both, in sequence. Bi-encoder retrieves the top few hundred from millions (fast); cross-encoder re-ranks just those hundreds (slow but precise, where the cost is affordable). Each does the job the other can't — the same recall-then-precision split as RecSys.
The encoder's pretraining objective decides whether its embeddings are usable. Raw BERT (trained with masked-LM) makes poor similarity embeddings; SBERT adds pooling + contrastive fine-tuning, and modern encoders (E5, BGE) trained with hard negatives push recall much higher — measured as recall@K, the fraction of queries whose correct document lands in the top K results returned. And every ANN index has a recall-vs-latency knob: HNSW's ef_search sets how many candidates stay in the search frontier during graph traversal (bigger ef_search = more of the graph explored = higher recall, higher latency), while IVF's nprobe sets how many inverted-list clusters get scanned per query (more clusters probed = more of the data actually checked = higher recall, higher latency). That knob must be calibrated on tail queries, not benchmarks — a 15ms P99 met on head queries will break on the tail.
Key points
- Bi-encoder for retrieval, cross-encoder for re-ranking — forced by scale, not preference. Cross-encoder models query×document interaction directly (more accurate) but is O(N) per query; bi-encoder precomputes document embeddings offline. Retrieve top 50–200 with the bi-encoder, re-rank with the cross-encoder.
- The pretraining objective determines embedding quality. MLM-trained BERT clusters poorly for similarity; contrastively fine-tuned encoders (SBERT → E5/BGE) with hard negatives are what make retrieval work. Don't reach for raw `bert-base` embeddings and expect recall.
- ANN indexes trade recall for latency, and tail queries are the binding constraint. Head queries hit high recall at a given ef_search/nprobe; tail queries don't. Calibrate the operating point on a stratified sample that includes the tail, or the SLA silently fails where it's least measured.
Semantic search is the RecSys funnel for text: a bi-encoder retrieves cheaply over millions and a cross-encoder re-ranks precisely over the survivors, with embedding quality set by the encoder's contrastive pretraining and the recall/latency knob calibrated on tail queries.
Recap
- Keyword (BM25) breaks on vocabulary mismatch; embeddings match on meaning: "heart attack symptoms" misses "myocardial infarction presentation" — same meaning, zero shared tokens. Semantic search maps queries and documents into a space where meaning, not token overlap, decides similarity.
- Cross-encoder vs bi-encoder is forced by scale, not preference: a cross-encoder feeds query and document in together (most accurate) but reruns per query-document pair → O(N)/query, so it caps at a few hundred docs = re-ranking only. A bi-encoder (two-tower) encodes each side separately (slightly less precise) so document embeddings are query-independent → precompute offline + ANN over billions = retrieval.
- Production uses both in sequence: bi-encoder retrieves the top few hundred from millions (fast), cross-encoder re-ranks just those hundreds (slow but precise, where the cost is affordable). The same recall-then-precision split as RecSys.
- Embedding quality is set by the pretraining objective: raw BERT trained with masked-LM makes poor similarity embeddings that don't cluster by meaning; SBERT adds pooling + contrastive fine-tuning, and E5/BGE trained with hard negatives push recall much higher. Don't reach for raw `bert-base` and expect recall.
- Every ANN index has a recall-vs-latency knob: HNSW's ef_search controls how many candidates stay in the search frontier during graph traversal (bigger = more explored = higher recall, higher latency); IVF's nprobe controls how many inverted-list clusters get scanned per query (more probed = higher recall, higher latency). Calibrate it on *tail* queries, not benchmarks. A 15ms P99 met on head queries breaks on the tail, because rare/poorly-covered queries need deeper traversal to reach the same recall.
Check your understanding
Q1. You need semantic search over 50M product descriptions with P99 < 15ms and recall@10 > 0.95. Which architecture fits?
- A) Run a cross-encoder over all 50M items in parallel on a very large GPU cluster for maximum precision, skipping the retrieval stage entirely.
- B) Bi-encoder embeddings in an HNSW index (ef_search≈100, ~2ms), then cross-encoder re-rank of the top 50 on GPU (~10ms) — ~12ms total.
- C) BM25 keyword retrieval for raw speed, paired with a cross-encoder re-ranker to recover semantic matches BM25 missed.
- D) A single bi-encoder using exact brute-force nearest-neighbor search, to guarantee full recall without any approximation.
Q2. A team uses raw `bert-base-uncased` [CLS] embeddings for semantic retrieval and gets poor recall. Why, and what's the minimal fix?
- A) BERT embeddings are simply too high-dimensional here; applying PCA down to 128 dimensions should make recall recover fully.
- B) BERT was pretrained with masked-LM, not a similarity objective, so embeddings don't cluster by meaning; fine-tune with contrastive pretraining.
- C) [CLS] pooling is the only real issue here; switching to a max-pooling scheme over tokens makes raw BERT work perfectly fine for retrieval overall.
- D) The index itself is the problem, not the encoder; switching FAISS-IVF over to HNSW alone should make recall recover fully.
Q3. Select the two correct statements about why an HNSW index meets P99 in load tests but violates it for a minority of production queries.
- A) ef_search was tuned on head queries; rare tail queries need deeper graph traversal to reach the same recall, exceeding budget.
- B) Calibrating the operating point on a stratified sample that includes tail queries — or explicitly capping ef_search — addresses the gap.
- C) HNSW is fundamentally non-deterministic, so the latency spikes are random noise that switching to IVF alone eliminates.
- D) Production embeddings quietly use a different float precision than the offline load test, which is unrelated to query type.
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →