learning-it by example

#49 RAG and vector search 5.6 min

HNSW vs IVF vs Flat: Vector Indexes Tested on 100k Vectors

I searched 100,000 vectors by looking at about 500, and still found nearly every right answer.

1. How does an IVF index search differently from a flat index?
2. In the video's faiss test on 100,000 made-up clustered vectors, what recall did the IVF index reach with nprobe 8, and about how many vectors did it compare per query?
3. In the video's faiss test, how is recall defined, and why is the flat index used as the answer key?
4. In the video's faiss test, the IVF 'compared per query' count is not the same kind of count as the HNSW one. Which comparisons does the IVF count leave out?
5. When does the video suggest moving from a flat index to an approximate one?

Practice only: nothing is saved and no score counts towards anything. Each answer comes with the reason.

  1. Read the test data

    Copy the code folder first. Open data.py and write down N, QUERIES, DIM and CLUSTERS. Predict how many vectors and how many queries make() returns, and the shape of each array. If numpy is installed, check with vectors, queries = make() and print vectors.shape and queries.shape. Then predict what the flat line in compare.py would print for compared per query if N were 50_000.

    A hint

    The flat index compares the query with every vector, so the work equals the number of vectors stored.

  2. More probes for IVF

    In compare.py change the IVF loop from (1, 8, 32) to (1, 2, 4, 8). Predict how recall and the number compared per query change as nprobe goes up, and guess the values for 2 and 4. If faiss-cpu 1.15.0 is installed, run python compare.py and compare. The video printed recall 0.83 at 1 probe and 1.00 at 8 probes.

    A hint

    More probes means more groups searched, so more work. Your numbers should lie between the video's values for 1 and 8.

  3. Widen the HNSW search

    In compare.py, add 128 to the efSearch loop (for ef in (16, 64)) so it reads (16, 64, 128). Predict what happens to recall, to the work per query and to the memory size. Then, if faiss is installed, run it and check. Say in one sentence why the memory is higher than for the flat and IVF indexes.

    A hint

    The video printed 40 MB for HNSW against 26 MB for the others, and the graph links are the extra cost.

  4. Change the number of results

    In compare.py change K from 10 to 5. Predict whether recall for ivf nprobe 1 and hnsw ef 16 goes up, down or stays about the same, and write down why before you run it. If you can run it, compare your prediction with the new output. Remember that the work counts are not times.

    A hint

    Recall is the share of the exact top K that the index also finds. There is no value in the video for K of 5, so treat this as your own experiment.

These tasks are for you to try on your own machine. Nothing is checked or saved.

What this does not show

100,000 made-up clustered vectors of 64 numbers and 200 queries, one seeded run; work is counted in comparisons, not time, and the IVF count leaves out the 316 group comparisons; adding, deleting and filtering were not tested.

Up next in RAG and vector search

More in RAG and vector search

All RAG and vector search videos

Related videos