Topic 6

Approximate nearest-neighbour search

Comparing a query with every vector is fine for thousands of chunks; Hands-On Large Language Models (Ch. 8, "Nearest neighbor search versus vector databases") says plain NumPy is reasonable up to tens of thousands. Beyond that, systems use approximate nearest-neighbour (ANN) search, which looks at only some of the vectors.

AI Engineering (Ch. 6, "Embedding-based retrieval") lists the main approaches; vector databases organise vectors into buckets, trees or graphs:

• IVF (inverted file index): k-means clusters; search only the clusters nearest the query. Together with product quantizationQuantizationStoring a model's numbers in a format with fewer bits, such as FP16, INT8 or INT4, to cut memory and the bytes each step reads. Strictly it means converting to integers, but in practice it covers any precision reduction.Where this is taught, the book calls it the backbone of FAISS.
• HNSW (Hierarchical Navigable Small World): a multi-layer graph of similar vectors, searched by walking its edges.
• LSH (locality-sensitive hashing): hash similar vectors into the same buckets.
• Product quantization: compress each vector into smaller sub-vectors so distances are cheaper.
• Annoy: several random binary trees, searched together.

There's a second trade, between indexing and querying. In "Comparing retrieval algorithms", the book contrasts HNSW, which gives high accuracy and fast queries but takes significant time and memory to build, with LSH, quicker and lighter to build but slower and less accurate to query. It points to the ANN-Benchmarks site, which compares algorithms on recall, queries per second, build time and index size.