Vector databases

1 min read
On trails:AGRAGstep 3/8

A vector database stores embeddings and returns the ones closest to a query vector. Comparing the query with every stored vector is too slow at scale, so the index uses approximate nearest neighbour (ANN) search: a little accuracy given up for a lot of speed.

Two indexes

Two ways to search approximately. IVF groups vectors into clusters and compares the query only with the nearest cluster. HNSW keeps layers of graphs: a search starts at the sparse top layer, takes long hops, then drops down to finer layers to reach the nearest vector. IVF: SEARCH THE NEAREST CLUSTERS probed query HNSW: HOP DOWN THE LAYERS layer 2 layer 1 layer 0 entry point nearest
IVF narrows by cluster, HNSW narrows by layer.

IVF (inverted file index) divides the vectors into clusters and searches only the nearest ones. The query is compared with the vectors in those clusters, never the whole set. If the true neighbour sits in a cluster that was skipped, it is missed.

HNSW (hierarchical navigable small world) is a graph of multi-connected layers. The top layer is sparse, with long hops. A search enters there, moves toward the query, then drops a layer and repeats, ending in the bottom layer that holds every vector. The paper credits the layering with logarithmic scaling.

One dial

Both are the same trade. IVF has nprobe, how many clusters to check. HNSW has efSearch, how widely to explore. More search effort means better recall and a slower query. Neither guarantees the exact nearest neighbour.

In LangChain the index lives behind the vector store, and the chain only calls similarity_search. How vectors get in is covered in ingestionRAG ingestionThe offline half of RAG: chunk the data, embed the chunks, save them in a vector database.Opens in a new tab, and what produces them in embeddingsEmbeddingsData turned into an array of numbers, placed so that similar meaning sits close together.Opens in a new tab.

Sources