centroid computation and -1 indices

[olivierabz]

Hi,

I am having trouble understanding the behaviour of faiss (and IndexIVFFlat) in a simple context of KNN where I sometimes get -1 indices instead of neighbours indices. I have read the documentation and previous issues about this topic and understand that -1 are retrieved when there are not enough neighbours in the searched cluster(s) to provide the expected total of k neighbours.

In my case, I only want 1 neighbour for each of my test vectors, and so I have set nprobe = 1, expecting to have at least one candidate vector in each cluster/list.

I produce the code provided below to illustrate/reproduce the problem. I generate a training set made of 2 times 10 unique vectors and I want to get the nearest neighbour for 10 test vectors (which are just translations of the unique training vectors).

The first thing we see is that despite having 10 unique vectors, each duplicated twice and setting nlist=10, I do not get centroids overlapping each points. Instead, I get two centroids that are very close to each other (the darker red circle on the figure) and I get a cluster in between two points.

When looking for neighbours for the 10 test vectors, I end up with one vector not getting any index (the point in purple).

I have 2 questions:

• why aren't all centroids at coordinates of existing points in my case?
• why do we get -1 for some test vectors while k=1?

Note that if I try with 30 vectors (i.e. 3 duplications of each original vectors), I don't get the same behaviour and get what I'd expect: 10 centroids overlapping the 10 unique vectors and no -1 index in the search step).

This behaviour is also dependent of the test values (behaviour not observed if I use X_test = np.array(unique_rows) + 0.75

Note that this is a minimalist example and that we have first observed this on a much larger dataset.

Any help in understand this would be greatly appreciated. Thanks.

import faiss
import math
import numpy as np
from numpy.typing import NDArray
import matplotlib.pyplot as plt

unique_rows = [
        [0.850276, -0.363280],
        [-0.703584, -0.726152],
        [-0.763625, -0.207147],
        [-0.591471, 1.194479],
        [0.495366, 0.270366],
        [0.395806, -1.086881],
        [-0.643693, 0.805122],
        [0.922869, -0.318901],
        [0.323212, -1.131260],
        [-0.776178, -0.770531],
    ]


X_train = np.tile(unique_rows, (20 // len(unique_rows), 1)) # -> Problem: 1 training row gets -1
# X_train = np.tile(unique_rows, (30 // len(unique_rows), 1)) # -> No problem: all rows get a neighbor
nlist = 10

X_test = np.array(unique_rows) + 0.5

# Fit
index = faiss.IndexFlatL2()

xb: NDArray[np.float64] = X_train.astype(np.float32)
size, dimension = X_train.shape

quantizer = faiss.IndexFlatL2(dimension)
index = faiss.IndexIVFFlat(
    quantizer, dimension, nlist, faiss.METRIC_L2
)

index.nprobe = 1
index.train(xb)
index.add(xb)
centroids = index.quantizer.reconstruct_n(0, nlist)

# Search
xq: NDArray[np.float64] = X_test.astype(np.float32)
distances, indices = index.search(xq, k=1)
distances = np.sqrt(distances)
has_index = [indices >= 0]

# Training points and centroids
fig, ax = plt.subplots()
ax.scatter(X_train[:, 0], X_train[:, 1], c='blue', marker='x', s=100, label='Data Points')
ax.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='o', s=100, alpha=0.5, label='Centroids')  
plt.title(f'training data ({X_train.shape[0]} points) and centroids (nlist={nlist})')
plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.legend()
plt.show()

# Testing points and centroids
fig, ax = plt.subplots()
ax.scatter(xq[:, 0], xq[:, 1], c=has_index, marker='x', s=100, label='Data Points')
ax.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='o', s=100, alpha=0.5, label='Centroids')
plt.title(f'testing data ({xq.shape[0]} points) and centroids (nprobe={index.nprobe})\n purple points are assigned a -1 index')
plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.legend()
plt.show()

Platform

macOS 10.13.2
Faiss version 1.8.0 installed