Part 5 of 6 · 4 min read
Exercises
Easy
Easy 1: Run and read (20 minutes)
In code/mini-vector, run python demo.py, python bench.py and pytest. For each demo query, say in one sentence why the top result won, and say which query shows that nearest-neighbour search never returns "nothing".
Done when: you can point to the exact line of output that proves the last claim.
Easy 2: Cosine by hand (15 minutes)
For a = (1, 2, 2) and b = (2, 0, 1), compute the dot product, both lengths and the cosine. Then check with cosine. Then compute the cosine of a with 10 * a and explain the result.
Done when: your hand result matches the code and you can say why scale does not matter.
Hint
|a| = 3 and |b| = sqrt(5); the dot product is 4.
Easy 3: Spot the missing synonym (20 minutes)
Write five short documents and five queries that should match them without sharing words. Predict which queries the toy embedder will get wrong (its concept table is small), then run them.
Done when: you have at least one correct hit, one miss, and a sentence explaining that a real model learns these links instead of using a hand-made table.
Hint
words must differ between query and document for the test to mean anything; punctuation and capitals are normalised.
Medium
Medium 1: Add a distance threshold (40 minutes)
Add search_with_scores(q, k, min_sim) to Exact that returns (index, similarity) pairs and drops results below min_sim. Use the demo documents and queries to choose a threshold, and show that the "holiday opening" query now returns nothing while the two good queries still work. Add three tests.
Done when: the three tests pass and you can explain what goes wrong if the threshold is set from only three queries.
Hint
the cosine of two unit vectors is their dot product, so data @ q already gives similarities.
Medium 2: Tune IVF (45 minutes)
Using bench.make_data, sweep n_clusters in 16, 64 and 256 and nprobe in 1, 4 and 16. For each of the nine settings print recall@10 and comparisons per query, then pick the cheapest setting that reaches recall of at least 0.95 and say why.
Done when: you have a nine-row table and a justified choice. Note which setting has the cheapest build and which has the cheapest query.
Hint
build time grows with n_clusters; query cost has a term for the centroids and a term for the lists searched.
Medium 3: Add deletion to the graph (60 minutes)
Add NSW.remove(i) that marks a point as deleted so searches never return it but still walk through it (a "tombstone"). Test that a removed point is never returned and that recall on the remaining points does not collapse after removing 20 percent of the data. Describe one problem with tombstones if you remove most of the data.
Done when: both tests pass and your written problem mentions wasted work or stale links.
Hint
keep a boolean list deleted; skip deleted ids only when collecting the final top k, not while walking.
Hard
Hard 1: Use a real embedding model (90 minutes)
Pick any real embedding model you can run (a local one, or a provider's embedding API). Embed the 12 questions and the chunks from module 1, then compare top-1 and top-3 with the keyword retriever from module 1. Report both tables and the three questions where the two methods disagree most. (I did not run this, so your numbers are the ground truth.)
Done when: you have both tables, three disagreements explained from the text, and one sentence on cost and latency of embedding.
Hint
normalise vectors to unit length before comparing, and check the model's documentation for whether queries need a special prefix.
Hard 2: Two-layer graph (90 minutes)
Extend NSW into a two-layer index: the top layer keeps a random 10 percent of the points with links among themselves; the search first finds the nearest top-layer point, then enters the bottom layer from there. Compare comparisons per query and recall with the one-layer version at the same ef on the benchmark data.
Done when: you have a table for both versions and a short statement of whether the second layer helped on this data, with the numbers (it is allowed not to help).
Hint
choose the top-layer points once with a seeded random generator, and build their links by exact search among themselves.
Hard 3: Product quantization sketch (90 minutes)
Split each 32-number vector into 4 parts of 8 numbers. For each part, run k-means with 16 centres on the data and store each vector as four small codes. Compute approximate distances from the codes using precomputed query-to-centre tables. Report memory (bytes per vector before and after), recall@10 of a full scan using the approximate distances, and the cost in comparisons.
Done when: you have the three measurements, a test that decoding then re-encoding a vector's code is stable, and a sentence on why this is usually combined with IVF.
Hint
for each query, compute a 4 by 16 table of distances to the centres once; the distance to any stored vector is then four table lookups added together.