NVIDIA / NVIDIA/cuvs

[BUG] Brute Force returns wrong distances

Open
#1,632 3 comments 0 reactions 1 assignee View on GitHub

@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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.