IndexIVFFlat with METRIC_L1 changes nprobe=1 Top-k after translating all vectors and queries

[mmnhgo]

Summary

IndexIVFFlat with METRIC_L1 can return a different Top-k result after applying the same translation vector to every database vector and every query, then rebuilding the index with the same deterministic training parameters.

A global translation is mathematically distance-preserving under the Manhattan/L1 metric:

||(x + c) - (q + c)||₁ = ||x - q||₁

In the reproduction below:

• the exact L1 Top-5 IDs are unchanged after translation;
• IndexIVFFlat with nprobe=nlist also returns the same Top-5 IDs;
• IndexIVFFlat with nprobe=1 returns a different Top-5 after translation.

This indicates that rebuilding the translated IVF index changes which candidate list is searched, even though the underlying nearest-neighbor problem remains equivalent.

---

Environment

API: Python
Faiss version: 1.14.2
Index: IndexIVFFlat
Metric: METRIC_L1
Dimension: 2
Database vectors: 500
Queries: 1
Number of inverted lists: 8
Search k: 5
Training seed: 123
Training iterations: 25

---

Minimal reproduction

import itertools

import faiss
import numpy as np


def topk_l1(xb, xq, k):
    distances = np.abs(
        xb[None, :, :].astype(np.float64)
        - xq[:, None, :].astype(np.float64)
    ).sum(axis=2)

    order = np.argsort(distances, axis=1)

    return (
        order[:, :k],
        np.take_along_axis(distances, order[:, :k], axis=1),
    )


def make_case():
    rng = np.random.default_rng(424242)

    target = (2, 500, 1, 8, 5, 1000, 50)

    for d, nb, nq, nlist, k, offmag in itertools.product(
        [2, 4, 8],
        [500, 1000],
        [1, 3],
        [8, 16],
        [5, 10],
        [10, 1000, 100000],
    ):
        for trial in range(80):
            xb = rng.normal(size=(nb, d)).astype("float32")
            xq = rng.normal(size=(nq, d)).astype("float32")

            offset = rng.normal(
                loc=offmag,
                scale=max(0.01, offmag * 0.01),
                size=d,
            ).astype("float32")

            if (
                d,
                nb,
                nq,
                nlist,
                k,
                offmag,
                trial,
            ) == target:
                return xb, xq, offset

    raise RuntimeError("target case not reached")


def build_ivf(xb, nprobe):
    d = xb.shape[1]

    quantizer = faiss.IndexFlat(d, faiss.METRIC_L1)

    index = faiss.IndexIVFFlat(
        quantizer,
        d,
        8,
        faiss.METRIC_L1,
    )

    index.cp.seed = 123
    index.cp.niter = 25

    index.train(xb)
    index.nprobe = nprobe
    index.add(xb)

    return index


print("faiss version:", getattr(faiss, "__version__", "unknown"))
print("numpy version:", np.__version__)

xb, xq, offset = make_case()

xb_translated = np.ascontiguousarray(xb + offset)
xq_translated = np.ascontiguousarray(xq + offset)

k = 5

# Exact float64 oracle.
exact_ids, exact_distances = topk_l1(xb, xq, k)
translated_exact_ids, translated_exact_distances = topk_l1(
    xb_translated,
    xq_translated,
    k,
)

# IVF with one probed list.
index = build_ivf(xb, 1)
translated_index = build_ivf(xb_translated, 1)

ivf_distances, ivf_ids = index.search(xq, k)
translated_ivf_distances, translated_ivf_ids = (
    translated_index.search(xq_translated, k)
)

# IVF full scan.
full_index = build_ivf(xb, 8)
translated_full_index = build_ivf(xb_translated, 8)

full_distances, full_ids = full_index.search(xq, k)
translated_full_distances, translated_full_ids = (
    translated_full_index.search(xq_translated, k)
)

print()
print(
    "config:",
    {
        "mr": "VectorTranslationMutator",
        "index": "IndexIVFFlat",
        "metric": "METRIC_L1",
        "d": 2,
        "nb": 500,
        "nlist": 8,
        "nprobe": 1,
        "k": 5,
        "offset": offset.tolist(),
    },
)

print()
print(
    "exact:",
    exact_ids.tolist(),
    exact_distances.tolist(),
)

print(
    "exact translated:",
    translated_exact_ids.tolist(),
    translated_exact_distances.tolist(),
)

print()
print(
    "IVF nprobe=1:",
    ivf_ids.tolist(),
    ivf_distances.tolist(),
)

print(
    "IVF translated nprobe=1:",
    translated_ivf_ids.tolist(),
    translated_ivf_distances.tolist(),
)

print()
print(
    "IVF nprobe=all:",
    full_ids.tolist(),
    full_distances.tolist(),
)

print(
    "IVF translated nprobe=all:",
    translated_full_ids.tolist(),
    translated_full_distances.tolist(),
)

exact_invariant = np.array_equal(
    exact_ids,
    translated_exact_ids,
)

full_scan_invariant = np.array_equal(
    full_ids,
    translated_full_ids,
)

single_probe_invariant = np.array_equal(
    ivf_ids,
    translated_ivf_ids,
)

print()
print("exact Top-k invariant:", exact_invariant)
print("IVF full-scan Top-k invariant:", full_scan_invariant)
print("IVF nprobe=1 Top-k invariant:", single_probe_invariant)

if (
    exact_invariant
    and full_scan_invariant
    and not single_probe_invariant
):
    print("BUG REPRODUCED")
else:
    raise SystemExit("bug not reproduced")

---

Observed behavior

The exact L1 search returns the same Top-5 IDs before and after translation:

Original exact Top-5:
[201, 439, 130, 58, 176]

Translated exact Top-5:
[201, 439, 130, 58, 176]

Scanning all IVF lists also preserves the Top-5:

Original IVF nprobe=nlist Top-5:
[201, 439, 130, 58, 176]

Translated IVF nprobe=nlist Top-5:
[201, 439, 130, 58, 176]

However, probing only one inverted list returns different IDs:

Original IVF nprobe=1 Top-5:
[130, 58, 233, 486, 360]

Translated IVF nprobe=1 Top-5:
[201, 439, 130, 58, 233]

The script prints:

exact Top-k invariant: True
IVF full-scan Top-k invariant: True
IVF nprobe=1 Top-k invariant: False
BUG REPRODUCED

---

Expected behavior

Applying the same translation to every database vector and query should preserve the L1 nearest-neighbor problem.

With the same data geometry, training seed, number of iterations, and IVF parameters, rebuilding the translated index should preserve the effective coarse candidate behavior, or at minimum return the same nprobe=1 Top-k IDs for this deterministic reproduction.

Expected translated nprobe=1 IDs:

[130, 58, 233, 486, 360]

---

Actual behavior

The translated IVF index returns:

[201, 439, 130, 58, 233]

instead of:

[130, 58, 233, 486, 360]

This happens even though:

exact original Top-5 == exact translated Top-5

and:

IVF full-scan original Top-5 == IVF full-scan translated Top-5

The difference therefore appears only when IVF candidate selection is restricted by nprobe.

---

Why this appears incorrect

For any vectors x, q, and translation vector c:

||(x + c) - (q + c)||₁
= ||x + c - q - c||₁
= ||x - q||₁

The translation does not change the mathematical L1 nearest-neighbor problem.

The exact float64 oracle confirms that the Top-5 ordering is unchanged for the generated test case.

A full IVF scan also returns the same Top-5 IDs, confirming that the indexed vectors and L1 search results remain consistent when every inverted list is searched.

The result changes only when nprobe=1, meaning the translated rebuild searches a different candidate subset.

There are no relevant exact-search ties explaining the changed result.

---

Impact

This makes approximate L1 search results sensitive to the absolute coordinate origin.

Equivalent datasets can produce different candidate lists and different Top-k results solely because every vector and query was shifted by the same constant offset.

This can affect applications that:

• center or uncenter embeddings;
• apply coordinate-system changes;
• add a global baseline to vector values;
• migrate between equivalent vector representations;
• compare independently rebuilt IVF indexes;
• expect deterministic training under a fixed random seed.

The issue is particularly visible at low nprobe, where a change in the selected coarse list directly changes the candidate set.

---

Control observations

Exact search is invariant

The float64 exact oracle returns the same Top-5 IDs before and after translation:

[201, 439, 130, 58, 176]

Full IVF scan is invariant

When nprobe is equal to nlist, both indexes return:

[201, 439, 130, 58, 176]

The result is deterministic

Both indexes use:

seed = 123
niter = 25

The reproduction uses a fixed NumPy seed and deterministically selects the same generated test case.

The behavior is specific to candidate pruning

The issue disappears when all inverted lists are searched.

This separates the behavior from the per-vector L1 distance calculation performed during the full scan.

---

Duplicate issue search

The following GitHub Issue and PR searches were checked:

L1 IVF translation nprobe
IndexIVFFlat METRIC_L1 translation
METRIC_L1 IVF translation invariant
L1 coarse quantizer translation
IndexIVFFlat global offset
IndexIVFFlat translated vectors
METRIC_L1 nprobe wrong result
IVF L1 candidate set
L1 centroid translation
VectorTranslationMutator IndexIVFFlat

Related but different reports include:

• IndexFlatL2 BLAS path returns zero distances and changes exact Top-k after uniform vector translation — IndexFlatL2 BLAS path returns zero distances and changes exact Top-k after uniform vector translation #5285
• IndexFlatPanorama L2 search returns wrong Top-1 after translating vectors and query — IndexFlatPanorama L2 search returns wrong Top-1 after translating vectors and query #5329
• IndexPQ inner-product Top-1 changes after appending constant record dimensions and zero query dimensions — IndexPQ inner-product Top-1 changes after appending constant record dimensions and zero query dimensions #5405
• Fix Jaccard heap selection in IVF search — PR Fix Jaccard heap selection in IVF search #5408

These reports involve different indexes, metrics, transformations, or failure modes.

No existing Issue was found for the specific combination:

IndexIVFFlat
METRIC_L1
global translation of database and queries
deterministic index rebuild
nprobe=1 candidate change
exact and full-IVF Top-k unchanged

---

Requested behavior

Please confirm whether changing the coarse candidate selection under a global L1-preserving translation is expected behavior for IndexIVFFlat.

If it is not expected, deterministic IndexIVFFlat training with METRIC_L1 should preserve its coarse candidate behavior under a global translation, subject only to genuine ties or explicitly documented floating-point limitations.

If this behavior is considered an accepted limitation of approximate IVF training with non-L2 metrics, documenting that low-nprobe results may depend on the absolute coordinate origin would help users understand and mitigate the issue.