IndexHNSWFlat can return invalid L2 results after IndexFlatL2 sync_l2norms() followed by add()

[mmnhgo]

Current Behavior

When using IndexHNSWFlat with METRIC_L2, calling sync_l2norms() on the underlying IndexFlatL2 storage after a partial add(), and then adding more vectors, can make HNSW return invalid L2 distances and inconsistent Top-k results.

This violates the dimension permutation invariance of L2 distance.

For L2 distance, if the same dimension permutation is applied to every database vector and every query vector, all pairwise distances should remain unchanged:

d(P(x), P(q)) = d(x, q)

Therefore, the squared L2 distances and Top-k labels should remain unchanged.

However, when the underlying IndexFlatL2 storage has stale cached_l2norms, IndexHNSWFlat can return different Top-k results before and after a common dimension permutation. It can also return negative squared L2 distances, which are invalid.

This is not normal ANN variance. The exact flat oracle confirms that the permutation preserves all expected L2 distances and Top-k IDs. The negative L2 distances indicate that invalid distance values are being computed.

Actual output on the affected path:

Expected exact Top-k for query row 0:

IDs: [128, 151, 157, 11, 145, 52, 33, 20, 109, 42]
D:   [3134.0, 3149.0, 3287.0, 3966.0, 4222.0, 5085.0, 5375.0, 5673.0, 6191.0, 6278.0]

Actual HNSW with stale norms before permutation:

IDs: [157, 128, 151, 163, 11, 145, 140, 148, 172, 191]
D:   [-7465.0, -4375.0, -3405.0, -1575.0, -629.0, 259.0, 289.0, 533.0, 567.0, 637.0]

Actual HNSW with stale norms after permutation:

IDs: [157, 128, 151, 163, 178, 11, 145, 140, 42, 148]
D:   [-7465.0, -4375.0, -3405.0, -1575.0, -913.0, -629.0, 259.0, 289.0, 387.26953125, 533.0]

Order comparison:

expected exact labels = [128, 151, 157, 11, 145, 52, 33, 20, 109, 42]
actual original labels = [157, 128, 151, 163, 11, 145, 140, 148, 172, 191]
actual permuted labels = [157, 128, 151, 163, 178, 11, 145, 140, 42, 148]

For example, squared L2 distances should never be negative, but the returned distances include values such as:

-7465.0
-4375.0
-3405.0
-1575.0

This happens after the following sequence:

1. Add a small first batch of vectors into IndexHNSWFlat.
2. Downcast the underlying storage to IndexFlatL2.
3. Call storage.sync_l2norms().
4. Add more vectors into the HNSW index.
5. Search with HNSW.

After step 4, cached_l2norms.size() remains smaller than ntotal, but HNSW search can still use the cached-norm distance computer.

Steps to Reproduce

The following script creates two IndexHNSWFlat indexes:

1. one with the original vectors;
2. one with the same dimension permutation applied to every database vector and query vector.

Both indexes call sync_l2norms() after a partial add, then add the remaining vectors. This leaves the underlying IndexFlatL2::cached_l2norms stale.

import faiss
import numpy as np

np.set_printoptions(precision=6, suppress=False)

seed = 0
d = 8
nb = 200
nq = 20
k = 10
first_batch = 10
M = 16
perm = np.array([3, 0, 7, 1, 6, 2, 5, 4])

rng = np.random.default_rng(seed)
xb = rng.integers(-50, 51, (nb, d)).astype("float32")
xq = rng.integers(-50, 51, (nq, d)).astype("float32")


def build_hnsw_with_stale_l2norms(vectors):
    index = faiss.IndexHNSWFlat(d, M, faiss.METRIC_L2)
    index.hnsw.efConstruction = 128
    index.hnsw.efSearch = 256

    index.add(vectors[:first_batch])

    storage = faiss.downcast_index(index.storage)
    storage.sync_l2norms()

    # This leaves cached_l2norms stale: size is still first_batch.
    index.add(vectors[first_batch:])
    return index


def flat_search(vectors, queries):
    index = faiss.IndexFlatL2(d)
    index.add(vectors)
    return index.search(queries, k)


D_gt, I_gt = flat_search(xb, xq)
D_gt_p, I_gt_p = flat_search(xb[:, perm], xq[:, perm])

assert np.array_equal(I_gt, I_gt_p)
assert np.array_equal(D_gt, D_gt_p)

idx = build_hnsw_with_stale_l2norms(xb)
idx_p = build_hnsw_with_stale_l2norms(xb[:, perm])

D, I = idx.search(xq, k)
D_p, I_p = idx_p.search(xq[:, perm], k)

row = int(np.where((I != I_p).any(axis=1))[0][0])

print("trigger_config:", {
    "index": "IndexHNSWFlat",
    "metric": "METRIC_L2",
    "d": d,
    "nb": nb,
    "nq": nq,
    "k": k,
    "M": M,
    "efConstruction": 128,
    "efSearch": 256,
    "first_batch_before_sync_l2norms": first_batch,
    "cached_l2norms_size_after_second_add": faiss.downcast_index(idx.storage).cached_l2norms.size(),
    "ntotal": idx.ntotal,
    "permutation": perm.tolist(),
})

print("violating_query_row:", row)
print("expected_topk_ids:", I_gt[row].tolist())
print("expected_distances:", D_gt[row].tolist())
print("actual_original_ids:", I[row].tolist())
print("actual_original_distances:", D[row].tolist())
print("actual_permuted_ids:", I_p[row].tolist())
print("actual_permuted_distances:", D_p[row].tolist())

if not np.array_equal(I, I_p):
    print("BUG REPRODUCED")
else:
    raise SystemExit("bug did not reproduce")

Expected Behavior

For squared L2 distance, applying the same dimension permutation to all stored vectors and all query vectors should preserve all pairwise distances.

Example:

q = [q0, q1, q2, q3]
x = [x0, x1, x2, x3]

perm = [2, 0, 3, 1]

P(q) = [q2, q0, q3, q1]
P(x) = [x2, x0, x3, x1]

The squared L2 distance remains unchanged:

||x - q||^2 = ||P(x) - P(q)||^2

Therefore, the Top-k labels and squared L2 distances should remain unchanged.

For the reproduction above, the exact flat oracle gives the expected Top-k for query row 0:

IDs: [128, 151, 157, 11, 145, 52, 33, 20, 109, 42]
D:   [3134.0, 3149.0, 3287.0, 3966.0, 4222.0, 5085.0, 5375.0, 5673.0, 6191.0, 6278.0]

The expected HNSW behavior is:

1. It may return approximate neighbors, but the returned L2 distances should be valid.
2. Squared L2 distances should never be negative.
3. A common dimension permutation should not change the actual L2 distance values.
4. If cached_l2norms is used, the cache should cover all vectors in the index.

Actual Behavior

IndexHNSWFlat returns invalid negative squared L2 distances and inconsistent Top-k results when cached_l2norms is stale.

The stale cache is created by:

index.add(first_batch)
storage.sync_l2norms()
index.add(remaining_vectors)

After the second add:

cached_l2norms.size() = 10
ntotal = 200

However, HNSW search can still use the cached-norm distance computer. For vectors added after sync_l2norms(), the distance computer may access norm entries beyond the cached norm array.

This produces invalid distances such as:

-7465.0
-4375.0
-3405.0
-1575.0

The exact flat oracle confirms that the dimension permutation itself preserves all expected L2 distances and Top-k IDs. Therefore, this is not caused by the metamorphic transformation.

[mnorris11]

It seems like a real issue. We will follow up in #5326.