merge_from corrupts the resulting index by default

[guillaumeguy]

Summary

Sharding index hydration is a common pattern for us.

After hydration, the user can then combine the indices with index.merge_from(index2). However, this could corrupt the index silently and it is very hard to debug (each individual index is fine, the merge is wrong). The right syntax is index.merge_from(index2, index.ntotal).

Unhelpfully, SO even recommends the bad syntax.

It would be nice to either default to the right pattern or emit a warning.

Platform

Linux 22.04

OS:

Faiss version:
1.8.0
Installed from:
pip
Faiss compilation options:

Running on:

• CPU
• GPU

Interface:

• C++
• Python

Reproduction instructions

# Pseudo-code

# Normal training
index_str = 'OPQ256_1280,IVF2048_HNSW32,PQ256x8'
index = faiss.index_factory(EMB_DIM, index_str, faiss.METRIC_INNER_PRODUCT)
faiss.normalize_L2(embs)
index.train(embs)

# Shard 1 
faiss.normalize_L2(embs)
index1.add(embs)

## shard 2 
faiss.normalize_L2(embs)
index2.add(embs)

# combine 
index1.merge_from(index2) 

# search
index1.search(q, 10) # This will return bad results

[kuarora]

Hi,

I see quite a few tests on merge_from in faiss/tests/test_merge_index.py
are you able to reproduce it with a standard dataset, or may be a test?

[guillaumeguy]

Hi @kuarora

Sure. See notebook attached.

https://gist.github.com/guillaumeguy/1f992f4f64e5180c8318f435f991d5ce

[pablocael]

Hi, can this be related to the issue I posted and was (imho wrongly) flaged as invalid? #3498

[guillaumeguy]

Hi @kuarora: Does the notebook work for you?

[mdouze]

Maybe we should re-visit this

[kuarora]

Hi @kuarora: Does the notebook work for you?

Yes, I am able to reproduce only when we don't use offset.
Once we discuss internally, I'll get back to you.

[mdouze]

There are two ways of constructing an IVF index:

• with add(): the ids are allocated sequentially by the index
• with add_with_ids(): the ids are provided by the user.

In the first case, when merging, the ids of the second index should be shifted to follow the ones from the first index (hence the add_id = index1.ntotal)
In the second case, we assume the user manages their own ids (that could be internal ids), so when merging, they should be left unchanged (add_id = 0).
Faiss does not keep track of which add or add_with_ids was used to populate the indexes, so it trusts the user to provide the add_id parameter to determine how the index should be processed.

Maybe we could issue a warning but it's not even clear in which of the two cases we should warn.

[kuarora]

Hi,

I had a chance to debug this issue further.

merge_from is working as expected and store codes and ids in list with closest centroid but reconstruct fails as direct map (array list invl) is expected to work with sequential ids and no-collision between ids. Once merge, it is very difficult to distinguish which embedding to return upon reconstruction if there is collision as offset for ids will be one last seen.

So, we can’t use directmap for reconstruction when there is id collision.

Possible warning we could throw when direct map is created. During its population, we can throw warning if id is already populated.
I was able to reproduce it with smaller dataset and ivfflat index, where ideally, reconstruction should have zero error.

Bento changes:

def run(q, embs1, embs2, single_index, offset=0):
    index1 = faiss.read_index(p)
    index2 = faiss.read_index(p)

    # index1 = faiss.index_factory(d, index_str, faiss.METRIC_INNER_PRODUCT)
    # index1.train(training_data)

    # index2 = faiss.index_factory(d, index_str, faiss.METRIC_INNER_PRODUCT)
    # index2.train(training_data)

    # Shard 1
    faiss.normalize_L2(embs1)
    index1.add(embs1)
    faiss.normalize_L2(embs2)

    ## shard 2
    if single_index:
        index1.add(embs2)
    else:
        index2.add(embs2)
        print(index1.ntotal, index2.ntotal)
        # combine
        # if offset > 0:
        #     index1.merge_from(index2, offset)
        # else:
        #     index1.merge_from(index2)
        index1.merge_from(index2, offset)
    print(index1.ntotal)

    # search
    D, I = index1.search(q, 5)
    print(D, I)
    faiss.extract_index_ivf(index1).make_direct_map()

    reconstructed = index1.reconstruct_batch([int(id) for id in np.ravel(I)])
    print (reconstructed)

    print(np.diagonal((reconstructed @ np.vstack([embs1, embs2])[np.ravel(I)].T)))


Compare following two 
# single index
run(q, embs1, embs2, True, 0)

# single index
run(q, embs1, embs2, False, 0)