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
- 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).
- 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.