[BUG] Brute Force returns wrong distances
Open
@jinsolp is already working on this.
Since Dec 11, 2025.
bug
- Dominant language
- Cuda
- Stars
- 854
- Forks
- 236
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 62
Description
Describe the bug
Our brute force implementation returns wrong distances
Steps/Code to reproduce bug
from sklearn.datasets import make_moons
import numpy as np
from cuvs.neighbors import brute_force, nn_descent
import cupy as cp
def calculate_l2exp_distance(X, i, j):
# Expanded L2: sqrt(||a||² + ||b||² - 2*a·b)
return np.sqrt(np.sum(X[i]**2) + np.sum(X[j]**2) - 2*np.sum(X[i]*X[j]))
def knn_recall(pred: np.ndarray, gt: np.ndarray) -> float:
N, k = pred.shape
correct = 0
for i in range(N):
pred_set = set(pred[i])
gt_set = set(gt[i])
correct += len(pred_set & gt_set)
return correct / (N * k)
# Add self-loops: discard last column, shift right, and add row index as first column
def add_self_loops(indices):
n_rows = indices.shape[0]
# Create array with self-loops in first column
self_loops = np.arange(n_rows).reshape(-1, 1)
# Drop last column and concatenate with self-loops at the beginning
return np.concatenate([self_loops, indices[:, :-1]], axis=1)
# Add zero distances for self-loops: discard last column, shift right, and add 0 as first column
def add_zero_loops(distances):
n_rows = distances.shape[0]
# Create array with zeros in first column (distance to self is 0)
zeros = np.zeros((n_rows, 1), dtype=distances.dtype)
# Drop last column and concatenate with zeros at the beginning
return np.concatenate([zeros, distances[:, :-1]], axis=1)
X, y = make_moons(n_samples=100_000, noise=0, random_state=42)
X = X.astype(np.float32)
metric = "l2"
k = 15
# Running our brute force index
index = brute_force.build(cp.array(X), metric=metric)
gpu_bf_distances, gpu_bf_indices = brute_force.search(index, cp.array(X), k)
gpu_bf_indices = gpu_bf_indices.copy_to_host()
gpu_bf_distances = gpu_bf_distances.copy_to_host()
print(f"gpu_bf_indices[2]: {gpu_bf_indices[2]}")
print(f"gpu_bf_distances[2]: {gpu_bf_distances[2]}")
# Running our nn descent index
build_params = nn_descent.IndexParams(metric=metric, return_distances=True, graph_degree=k, dist_comp_dtype="fp32")
index = nn_descent.build(build_params, X)
gpu_nnd_indices = add_self_loops(index.graph)
gpu_nnd_distances = add_zero_loops(index.distances)
print(f"gpu_nnd_indices[2]: {gpu_nnd_indices[2]}")
print(f"gpu_nnd_distances[2]: {gpu_nnd_distances[2]}")
print(f"l2 distance between 2 and 23: {calculate_l2exp_distance(X, 2, 23)}")
print(f"l2 distance between 2 and 99314: {calculate_l2exp_distance(X, 2, 99314)}")
print(f"recall: {knn_recall(gpu_bf_indices, gpu_nnd_indices)}")
Prints the following
gpu_bf_indices[2]: [ 2 23 93 193 298 430 499 709 543 801 962 1028 1190 1064 1071]
gpu_bf_distances[2]: [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
gpu_nnd_indices[2]: [ 2 28031 37026 45329 52627 59376 61898 83218 92058 10229 31483 67305
71171 88253 99314]
gpu_nnd_distances[2]: [0. 0. 0. 0. 0. 0.
0. 0. 0. 0.00034527 0.00034527 0.00034527
0.00034527 0.00034527 0.00034527]
l2 distance between 2 and 23: 0.026199372485280037 # larger distance than first k=15
l2 distance between 2 and 99314: 0.0003452669770922512 # can see that nn descent returns correct distance
recall: 0.5153706666666666
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.