IndexIVFFlatDedup.reset() leaves stale duplicate-chain IDs searchable

[leemeii]

Environment

• Faiss: faiss-cpu==1.15.0
• Index: IndexIVFFlatDedup
• Metric: METRIC_L2

Summary

IndexIVFFlatDedup.reset() clears the physical inverted lists and resets ntotal, but leaves the duplicate-chain map instances populated.

After reset, an old duplicate ID can become searchable again when its old representative ID is re-added. The index reports the correct new ntotal, but search returns an ID that was removed by reset().

Minimal reproduction

import faiss
import numpy as np

x = np.array([[0.0], [0.0]], dtype="float32")

index = faiss.IndexIVFFlatDedup(
    faiss.IndexFlatL2(1),
    1,
    1,
)

index.train(x)
index.add_with_ids(
    x,
    np.array([403, 404], dtype="int64"),
)

index.reset()

index.add_with_ids(
    x[:1],
    np.array([403], dtype="int64"),
)

D, I = index.search(x[:1], 2)

print("ntotal:", index.ntotal)
print("distances:", D)
print("labels:", I)

Expected behavior

After reset(), only the newly added ID 403 should be active.

The removed ID 404 must not appear in search results:

ntotal: 1
labels: [403, -1]

The second result may be an empty-result sentinel because only one logical vector is active.

Actual behavior

ntotal: 1
labels: [403, 404]
distances: [0.0, 0.0]

The stale ID 404 is returned even though it was removed by reset().

The behavior reproduced in 10/10 fresh processes. Because nlist=1 and nprobe=1, this is not approximate-search recall variance.

Root cause

IndexIVFFlatDedup stores duplicate logical IDs in:

std::unordered_multimap<idx_t, idx_t> instances;

When vectors 403 and 404 are added with identical contents, one physical representative is stored and the duplicate relationship is recorded in instances.

The inherited IVF reset clears the inverted lists and ntotal, but does not clear instances.

After reset:

1. the old physical entry and ntotal are cleared;
2. the stale mapping 403 -> 404 remains in instances;
3. ID 403 is added again as a new physical representative;
4. search finds 403 and expands the stale duplicate chain, returning 404.

The deduplication search path expands entries from instances, while remove_ids() explicitly updates that map. There is no corresponding reset override.

Relevant source:

• [IndexIVFFlat.h](https://github.com/facebookresearch/faiss/blob/v1.15.0/faiss/IndexIVFFlat.h)
• [IndexIVFFlat.cpp](https://github.com/facebookresearch/faiss/blob/v1.15.0/faiss/IndexIVFFlat.cpp)
• [IndexIVF.cpp](https://github.com/facebookresearch/faiss/blob/v1.15.0/faiss/IndexIVF.cpp)

The same missing reset cleanup is present in the current main source at the time of this report.

Impact

Applications may receive external IDs that are no longer present in the index. This can corrupt:

• deletion and reinsertion workflows;
• ID-to-vector lookups;
• result filtering;
• pagination;
• lifecycle and cardinality checks.

The index reports ntotal=1, so callers may trust the metadata while receiving two logical IDs.

Suggested fix

Override reset() in IndexIVFFlatDedup:

void reset() override {
    IndexIVF::reset();
    instances.clear();
}

The exact base call can follow the existing class hierarchy, but instances must be cleared whenever the physical index is reset.

Add a regression test covering:

1. adding two identical vectors with IDs 403 and 404;
2. calling reset();
3. re-adding only ID 403;
4. verifying that ID 404 is absent from search results;
5. verifying ntotal == 1.

Duplicate search

A bounded search found no exact report for this reset and stale-duplicate-chain behavior.

Issue #5566 and PR #5570 concern incorrect remove_ids counts for duplicate IDs. PR #5440 concerns null storage in composite indexes. These use different causes and code paths.