← All Cracked ML projects
PL-B09NOT STARTEDBEGINNERMLPYTHONIMPACT ★★☆☆☆

Vector search from scratch: IVF-PQ vs FAISS

Go from brute force to IVF to product quantisation in NumPy, scored on the recall-vs-QPS (queries per second) curve that ann-benchmarks uses.

EST.8 h
REWARD+200 XP
AFTERANN-Benchmarks + 1

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
recall@10 (the fraction of the true 10 nearest neighbours you return) vs queries/sec curve on glove-100-angular; index RAM
GOAL · recall@10 ≥ 0.90 at ≥ 50% of FAISS IVF-Flat's QPS; IVF-PQ index ≤ 1/8 of the float index size at recall@10 ≥ 0.80
FAISS IndexIVFFlat / IndexIVFPQ (ann-benchmarks protocol) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Build exact cosine kNN with a blocked matmul (process queries in chunks so memory stays bounded) and argpartition (find the top k without sorting everything). Then build IVF-Flat using your k-means from PL-B05, the palette project. IVF (an inverted file index) clusters the vectors and, at query time, searches only the few clusters nearest to the query. Then build IVF-PQ with asymmetric distance tables. PQ (product quantisation) splits each vector into sub-vectors and replaces each sub-vector with the ID of its nearest centroid from a small codebook, so a vector takes a few bytes. Asymmetric distance tables precompute the distance from the raw query to every codebook centroid, so each comparison becomes a few table lookups. Evaluate on glove-100-angular from ann-benchmarks, single-thread, with the same nlist (number of clusters) and nprobe (clusters searched per query) as FAISS.

VICTORY CONDITIONS

  1. recall@10 ≥ 0.90 at ≥ 50% of FAISS IVF-Flat's QPS; IVF-PQ index ≤ 1/8 of the float index size at recall@10 ≥ 0.80 (recall@10 (the fraction of the true 10 nearest neighbours you return) vs queries/sec curve on glove-100-angular; index RAM).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

IVF (inverted file index)
Cluster the database vectors, then search only the clusters closest to the query instead of every vector.
Product quantisation (PQ)
Compress a vector by splitting it into pieces and storing, for each piece, the ID of the closest entry in a small codebook.
Asymmetric distance
Compare the uncompressed query against compressed database vectors using precomputed lookup tables.
recall@10
Of the true 10 nearest neighbours, the fraction your search actually returned.
QPS
Queries per second, the speed side of the speed-versus-accuracy trade-off.

Why it rates ★★☆☆☆

Every RAG stack (retrieval-augmented generation, where an LLM looks up documents before answering) depends on this, and knowing why PQ works is a real interview edge.