[BUG] Some values of graphDegree and intermediateGraphDegree resulting in cagra build errors

[chatman]

Describe the bug
Just found a situation where numdocs= 101, dimensions=128, graphdegree=64 and intGraphDegree=64 fails, but graphDegree=1, intGraphDegree=2 passes.

Steps/Code to reproduce bug
Index 101 vectors (dim=128) with graphDegree=64, intermediateGraphDegree=64. There's the following error:

cuvsCagraBuild: 0
RAFT failure at file=/home/searchscale/code/cuvs-api/cuvs/cpp/src/neighbors/detail/cagra/graph_core.cuh line=1252: Could not generate an intermediate CAGRA graph because the initial kNN graph contains too many invalid or duplicated neighbor nodes. This error can occur, for example, if too many overflows occur during the norm computation between the dataset vectors.
Obtained 7 stack frames
........

Expected behavior
If those degrees are bad values, some sensible defaults should be assumed by cuvs. Just like it assumes some defaults if those degrees are more than the dataset size. FYI, using 64/128 as degrees fails, even though cuvs drops them back to 100 (less than the dataset size), so even cuvs' own chosen defaults are failing.

If this is not a bug, but a user error, then this needs to be handled in the (upcoming) Java API appropriately.

Environment details (please complete the following information):

• Environment location: [Bare metal, RTX 4090]
• Method of RAFT install: [from source]

Additional context
Branch 25.02.
Found this while trying via the Java API. Haven't tested with C api directly yet. In my experience, using both degrees as 32 passes, but 33 fails. Dataset doesn't contain any duplicates.

[rhdong]

Hi @chatman, thank you for the feedback! It would be helpful if you could provide a minimal reproducible code.

[lowener]

I was running into this error yesterday so I already have a reproducer available as a gtest:

/*
 * Copyright (c) 2024, NVIDIA CORPORATION.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <gtest/gtest.h>

#include "../ann_cagra.cuh"

#include <cuvs/neighbors/cagra.hpp>

#include <raft/core/device_mdarray.hpp>
#include <raft/core/device_resources.hpp>

#include <cstdint>

namespace cuvs::neighbors::cagra {

class AnnCagraBugSmallDataset : public ::testing::TestWithParam<cagra::search_algo> {
 public:
  using data_type = half;

 protected:
  void run()
  {
    cagra::index_params cagra_index_params;
    cagra_index_params.graph_degree              = 3;
    cagra_index_params.intermediate_graph_degree = 3;
    auto nn_descent_params = graph_build_params::nn_descent_params(
        cagra_index_params.intermediate_graph_degree);
    nn_descent_params.intermediate_graph_degree = 4;
    cagra_index_params.graph_build_params = nn_descent_params;
    /*
    cagra_index_params.graph_build_params = graph_build_params::ivf_pq_params(dataset->extents(),
      metric);*/
    auto cagra_index =
      cagra::build(res, cagra_index_params, raft::make_const_mdspan(dataset->view()));

    cagra::search_params cagra_search_params;
    cagra_search_params.itopk_size        = 5;
    cagra_search_params.algo = ::testing::TestWithParam<cagra::search_algo>::GetParam();

    // NOTE: when using one resource/stream for everything, the bug is NOT reproducible
    raft::resources res_search;
    cagra::search(res_search,
                  cagra_search_params,
                  cagra_index,
                  raft::make_const_mdspan(queries->view()),
                  neighbors->view(),
                  distances->view());

    raft::resource::sync_stream(res_search);
  }

  void SetUp() override
  {
    dataset.emplace(raft::make_device_matrix<data_type, int64_t>(res, n_samples, n_dim));
    queries.emplace(raft::make_device_matrix<data_type, int64_t>(res, n_queries, n_dim));
    neighbors.emplace(raft::make_device_matrix<uint32_t, int64_t>(res, n_queries, k));
    distances.emplace(raft::make_device_matrix<float, int64_t>(res, n_queries, k));
    raft::random::RngState r(1234ULL);
    InitDataset(res, dataset->data_handle(), n_samples, n_dim, metric, r);
    raft::linalg::map(
      res, queries->view(), raft::const_op<data_type>{raft::upper_bound<data_type>()});
    raft::resource::sync_stream(res);
  }

  void TearDown() override
  {
    dataset.reset();
    queries.reset();
    neighbors.reset();
    distances.reset();
    raft::resource::sync_stream(res);
  }

 private:
  raft::resources res;
  std::optional<raft::device_matrix<data_type, int64_t>> dataset  = std::nullopt;
  std::optional<raft::device_matrix<data_type, int64_t>> queries  = std::nullopt;
  std::optional<raft::device_matrix<uint32_t, int64_t>> neighbors = std::nullopt;
  std::optional<raft::device_matrix<float, int64_t>> distances    = std::nullopt;

  constexpr static int64_t n_samples                   = 25;
  constexpr static int64_t n_dim                       = 128;
  constexpr static int64_t n_queries                   = 30;
  constexpr static int64_t k                           = 2;
  constexpr static cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded;
};

TEST_P(AnnCagraBugSmallDataset, AnnCagraBugSmallDataset) { this->run(); }

INSTANTIATE_TEST_CASE_P(AnnCagraBugSmallDatasetReproducer,
                        AnnCagraBugSmallDataset,
                        ::testing::Values(cagra::search_algo::MULTI_CTA));

}  // namespace cuvs::neighbors::cagra