IVF65536_HNSW32,PQ32 much better than HNSW32_PQ32?

[miguelwon]

I did the following experience.

I have 4M normalized embeddings with dimension 768 and tested the creation of two indexes. The first one with the code:

index_1 = faiss.index_factory(768, 'IVF65536_HNSW32,PQ32', faiss.METRIC_INNER_PRODUCT)
index_1.train(embs)
index_1.add(embs)

and the second one with:

index_2 = faiss.index_factory(768, 'HNSW32_PQ32', faiss.METRIC_INNER_PRODUCT)
index_2.train(embs)
index_2.add(embs)

where embs is a numpy array with the 4M vectors.

I then did a small test to check the 1-recall@10 when searching of a random sample of the same vectors:

n_sample = 10000
inds = np.random.randint(0, embs.shape[0], n_sample)

With the first index I got:

count = 0
for idx in inds:
    arr = embs[idx:idx+1,:]
    scores,indices = index_1.search(arr,k=10)
    if idx in indices:
        # print(i,ind)
        count += 1
print(count/n_sample)
0.8069

for the second one:

count = 0
for idx in inds:
    arr = embs[idx:idx+1,:]
    scores,indices = index_2.search(arr,k=10)
    if idx in indices:
        count += 1
print(count/n_sample)
0.9943

The first index is only 375M and the second one, 1.2G. These results are quite surprising and I was actually expecting the opposite.

What am I doing wrong?

[siddhsql]

I am also trying to learn but I think the results make sense. IVF65536_HNSW32,PQ32 is not better than HNSW32_PQ32. the accuracy of HSNW32_PQ32 is higher (0.9943 vs 0.8069). where it suffers is memory consumption. the higher memory consumption is also expected.

HNSW32_PQ32 is storing compressed vectors. Each vector is compressed to 32 bytes. And you have 64 links in the base layer. Each link needs 4 bytes (unsigned integer). 64 links = 256 bytes. per vector we have 288 bytes. for 4M vectors this translates to 1,152,000,000 which is close to your observation of 1.2G (note I did not factor in storage by higher layers of HNSW).

IVF65536_HNSW32,PQ32 is going to store 4M vectors in 65536 clusters. the storage of the vectors will take up 32 bytes per vector * 4M vectors = 128,000,000 bytes. Now we need to account for storage of the inverted list. The list has 65536 clusters. Each cluster contains the IDs of the vectors in that cluster. To store 4M Ids you will need another 16,000,000 bytes. We are also creating a HNSW graph of 65536 data points. this will cost 65536 vectors * 4 bytes per vector (each vector is the centroid of the cluster) + 64 links per vector * 4 bytes per link * 65536 vectors = 17,039,360 bytes. lets add up to get

128000000.0+16000000+17039360
161,039,360.0 bytes

compare to 375M which is about 2x.