Exercise 11 — Embedding Search

Timebox: 30-45 minutes

Goal

Build a tiny vector search: cosine similarity over an in-memory store, then add a quick approximate-NN trick. Useful as a RAG-eval primitive.

Work in

• embedding_search.py

Tasks

1. cosine(u, v) — pure NumPy.
2. Index.add(id, vec) and Index.search(query, k) returning top-k by cosine.
3. Normalize vectors on insert so search is a single matmul.
4. Add a simple ANN path: random projection LSH or IVF (assign vectors to centroids, search only nearest M centroids' shards).
5. Measure recall@k of ANN against exact for a synthetic corpus.

Done when

• Exact and ANN paths both work
• Recall@10 and latency printed for both on a 10K-vector synthetic corpus
• You can explain why normalization makes cosine == dot product

Stretch

• Plug in real embeddings (sentence-transformers) and search over a small text corpus
• Add filtering (metadata predicate at search time)