Vector Embeddings & ANN Search

Semantic search and recommendations increasingly rely on vector embeddings and approximate nearest-neighbor indexes. We trade exact recall for speed at billion-vector scale.

Embeddings turn "find similar meaning" into "find nearest points in high-dimensional space." ANN indexes trade perfect accuracy for speed — interview answer: retrieve candidates with ANN, rerank with a heavier model.

Vector search finds nearest neighbors in embedding space — core to RAG, recommendations, and semantic search. Three lenses:

Walk RAG retrieval as interview steps. Step 1 — Embed: chunk documents, generate vectors via embedding model. Step 2 — Index: insert into ANN index (HNSW, IVF). Step 3 — Query: embed user question, k-NN search returns top-k chunks. Step 4 — Augment: inject chunks into LLM prompt context. Step 5 — Filter: metadata pre-filter before ANN to reduce search space.

Cosine similarity computation

import numpy as np

def cosine_similarity(a: np.ndarray, b: np.ndarray) -> float:
    return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))

# Pre-normalize vectors at index time → cosine == dot product (faster ANN)
def normalize(v: np.ndarray) -> np.ndarray:
    return v / np.linalg.norm(v)

# Hybrid score (common interview pattern)
final_score = 0.3 * bm25_score + 0.7 * cosine_sim

HNSW vs IVF, cosine vs dot product, dimension trade-offs — we compare:

• Similarity metrics — pick one and stay consistent across index and query:

• ANN index families — the index choice drives latency, memory, and recall:

• Dimensionality: 384–768 common for sentence transformers; 1536 for OpenAI ada; higher dims ≠ always better — match model to use case.
• Sharding: partition index by category, geography, or consistent hash; fan-out query to shards, merge top-K globally.
• Freshness: new items need embedding + incremental index insert; batch nightly rebuild vs online HNSW insert trade latency vs consistency.

Semantic recall trades index build cost, memory, and approximate accuracy — we state both:

Two-stage retrieval is the standard interview pattern: ANN returns 200–1000 cheap candidates; a cross-encoder or learning-to-rank model reranks to top 10–20. Never run a cross-encoder on the full billion-item corpus.

Stale embeddings, cold-start, and hallucination from bad retrieval — we name mitigations:

RAG chatbots, product recommendations, and image similarity use vector search:

Add vector DB when similarity search on embeddings is the core query pattern:

Vector search connects to data serialization, stream ingestion, and Applied AI interview patterns:

• #10 Indexing & Query Optimization — inverted indexes for sparse BM25 complement dense ANN indexes.
• #12 Caching Patterns — cache hot query embeddings and top-K results for trending searches.
• #48 Recommendation System (problem) — two-tower embeddings + ANN candidate retrieval + rerank.
• #101 Search Ranking (Learning to Rank) (problem) — ANN recall stage feeding LTR reranker.
• #111 Document QA Platform (RAG) (problem) — chunk embeddings, vector DB retrieval, LLM generation.
• #12 Search Engine (problem) — hybrid sparse + dense retrieval pipeline.

HNSW Internals (Interview Sketch)

Hierarchical Navigable Small World builds a multi-layer graph. Layer 0 contains every vector with dense local links. Upper layers are subsamples with longer jumps. Search starts at the entry point in the top sparse layer, greedily moves to the nearest neighbor until stuck, drops to the next layer, repeats until layer 0, then expands a candidate list controlled by ef_search.

• ef_construction (build time): higher → better graph quality, slower index build.
• ef_search (query time): higher → better recall, higher latency.
• M (max neighbors per node): 16–48 typical; higher M → more RAM, better recall.

IVF + PQ Memory Math

IVF with 4096 centroids partitions vectors into clusters. At query time, probe the nearest nprobe centroids (e.g., 32 of 4096) — search only ~1% of the corpus. Product Quantization splits each 768-dim vector into 96 sub-vectors of 8 dims, each mapped to one of 256 centroids (1 byte each) → 96 bytes vs 3072 bytes raw, with approximate distance via lookup tables.

Hybrid Sparse + Dense Retrieval

# Reciprocal Rank Fusion (RRF) — no score normalization needed
def rrf_score(rank_sparse, rank_dense, k=60):
    return 1/(k + rank_sparse) + 1/(k + rank_dense)

# Pipeline:
# 1. BM25 top-100 from Elasticsearch
# 2. ANN top-100 from Milvus/FAISS
# 3. Merge by doc_id, compute RRF, return top-20
# 4. Cross-encoder rerank top-20 → final top-10

Sparse catches exact entity names and SKUs; dense catches paraphrases ("laptop" ↔ "notebook computer"). Problem #101 extends this with a learning-to-rank model on hand-crafted + embedding features.

RAG Chunking Strategy

For problem #111: split documents into 256–512 token chunks with 50-token overlap; embed each chunk; store chunk_id → (doc_id, offset, vector). At query time, retrieve top-K chunks, dedupe by doc_id, pass to LLM with citation metadata. Re-rank chunks with a cross-encoder before context assembly to reduce hallucination surface.

FAISS Quick Reference

• IndexFlatL2 — exact brute force; baseline for recall benchmarks.
• IndexIVFPQ — IVF + PQ; billion-scale with RAM constraints.
• IndexHNSWFlat — HNSW without compression; best recall/latency for RAM-rich deployments.
• GPU indexes (GpuIndexIVFPQ) for batch embedding ingestion and high-QPS serving.