NVIDIA / NVIDIA/cuvs

[BUG] `pairwise_distances` returns different distances for `InnerProduct` metric

Open
#1,056 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug C++
Dominant language
Cuda
Stars
854
Forks
236
Avg merge
3d 3h
Merged PRs (30d)
62

Description

Describe the bug
cuvs::distance::pairwise_distance function returns different distances when they should be the same.

Given dataset X of size n x dim the following have different values for relatively small N and likely prime values of dim.

  • distance between vector 0 and vector 1 by running pairwise_dist(X, X) -> resulting in distances matrix n x n
  • distance between vector 0 and vector 1 by running pairwise_dist(X[:512], X) -> resulting in distances matrix 512 x n

Steps/Code to reproduce bug

#include <cuvs/distance/distance.hpp>

#include <raft/random/make_blobs.cuh>
#include <raft/core/device_mdarray.hpp>
#include <raft/core/host_mdarray.hpp>
#include <raft/core/device_mdspan.hpp>

#include <iostream>

void compare(const raft::resources& handle, size_t n_rows, size_t dim, cuvs::distance::DistanceType metric) {
    auto dataset = raft::make_device_matrix<float, int64_t>(handle, n_rows, dim);
    auto labels = raft::make_device_vector<int64_t, int64_t>(handle, n_rows);
    raft::random::make_blobs(handle, dataset.view(), labels.view()); 

    // search on the entire dataset. resulting output distance is n_rows x n_rows
    auto out_pairwise_dists = raft::make_device_matrix<float, int64_t>(handle, n_rows, n_rows);
    cuvs::distance::pairwise_distance(
        handle,
        raft::make_const_mdspan(dataset.view()),
        raft::make_const_mdspan(dataset.view()),
        out_pairwise_dists.view(),
        metric,
        2.0);
    
    // this holds distance between vector 0 and vector 1
    float vec0_vs_vec1;
    raft::copy(&vec0_vs_vec1, out_pairwise_dists.data_handle()+1, 1, raft::resource::get_cuda_stream(handle));

    // make search matrix the first 512 rows. Resulting output distances is 512 x n_rows
    size_t tile_size = 512;
    auto out_pairwise_dists_tiled = raft::make_device_matrix<float, int64_t>(handle, tile_size, n_rows);
    auto tiled_search_matrix_view = raft::make_device_matrix_view<float, int64_t>(dataset.data_handle(), tile_size, dim);
    cuvs::distance::pairwise_distance(
        handle,
        raft::make_const_mdspan(tiled_search_matrix_view),
        raft::make_const_mdspan(dataset.view()),
        out_pairwise_dists_tiled.view(),
        metric,
        2.0);
    
    // this holds distance between vector 0 and vector 1
    float vec0_vs_vec1_tiled;
    raft::copy(&vec0_vs_vec1_tiled, out_pairwise_dists_tiled.data_handle()+1, 1, raft::resource::get_cuda_stream(handle));
    
    std::cout << "for n rows " << n_rows << " and dim " << dim << " ";
    if (vec0_vs_vec1 == vec0_vs_vec1_tiled) {
        std::cout << "same result between full pairwise dist and tiled pairwise dist\n";
    } else {
        std::cout << "mismatch! distance from full pairwise dist " << vec0_vs_vec1 << " and distance from tile pairwise dist " << vec0_vs_vec1_tiled << std::endl;
    }
}

int main() {
    std::cout << std::fixed << std::setprecision(std::numeric_limits<float>::max_digits10);
    raft::resources handle;

   compare(handle, 1000, 64, cuvs::distance::DistanceType::InnerProduct);  // CORRECT
    compare(handle, 1000, 137, cuvs::distance::DistanceType::InnerProduct); // WRONG
    compare(handle, 1000, 131, cuvs::distance::DistanceType::InnerProduct); // WRONG
    compare(handle, 1000, 47, cuvs::distance::DistanceType::InnerProduct);  // CORRECT
    compare(handle, 1000, 128, cuvs::distance::DistanceType::InnerProduct); // CORRECT
    compare(handle, 2000, 137, cuvs::distance::DistanceType::InnerProduct); // CORRECT
    compare(handle, 5000, 137, cuvs::distance::DistanceType::InnerProduct); // CORRECT

    compare(handle, 1000, 64, cuvs::distance::DistanceType::L2SqrtExpanded);  // CORRECT
    compare(handle, 1000, 137, cuvs::distance::DistanceType::L2SqrtExpanded); // CORRECT
    compare(handle, 1000, 131, cuvs::distance::DistanceType::L2SqrtExpanded); // CORRECT
    compare(handle, 1000, 47, cuvs::distance::DistanceType::L2SqrtExpanded);  // CORRECT
    compare(handle, 1000, 128, cuvs::distance::DistanceType::L2SqrtExpanded); // CORRECT
    compare(handle, 2000, 137, cuvs::distance::DistanceType::L2SqrtExpanded); // CORRECT
    compare(handle, 5000, 137, cuvs::distance::DistanceType::L2SqrtExpanded); // CORRECT

    compare(handle, 1000, 64, cuvs::distance::DistanceType::L2Expanded);  // CORRECT
    compare(handle, 1000, 137, cuvs::distance::DistanceType::L2Expanded); // CORRECT
    compare(handle, 1000, 131, cuvs::distance::DistanceType::L2Expanded); // CORRECT
    compare(handle, 1000, 47, cuvs::distance::DistanceType::L2Expanded);  // CORRECT
    compare(handle, 1000, 128, cuvs::distance::DistanceType::L2Expanded); // CORRECT
    compare(handle, 2000, 137, cuvs::distance::DistanceType::L2Expanded); // CORRECT
    compare(handle, 5000, 137, cuvs::distance::DistanceType::L2Expanded); // CORRECT
    
    return 0;
}

[Printed result]

for n rows 1000 and dim 64 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 137 mismatch! distance from full pairwise dist -888.654418945 and distance from tile pairwise dist -888.654602051
for n rows 1000 and dim 131 mismatch! distance from full pairwise dist -43.031589508 and distance from tile pairwise dist -43.031539917
for n rows 1000 and dim 47 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 128 same result between full pairwise dist and tiled pairwise dist
for n rows 2000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 5000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 64 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 131 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 47 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 128 same result between full pairwise dist and tiled pairwise dist
for n rows 2000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 5000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 64 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 131 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 47 same result between full pairwise dist and tiled pairwise dist
for n rows 1000 and dim 128 same result between full pairwise dist and tiled pairwise dist
for n rows 2000 and dim 137 same result between full pairwise dist and tiled pairwise dist
for n rows 5000 and dim 137 same result between full pairwise dist and tiled pairwise dist

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.

Research direction

Start at cuvs::distance::pairwise_distance and trace the InnerProduct path used for full and tiled inputs. Reproduce the mismatch with the supplied dimensions, then verify that the distances match for those cases while the listed L2 metrics remain unchanged.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
machine-learning, performance, search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.