[BUG] CAGRA: calc_hashmap_params() never terminates for large itopk_size (hash_bitlen limit is checked after the sizing loop)

[shaunakkapur]

Describe the bug

search_plan_impl::calc_hashmap_params() sizes its hash tables with loops of the form

hash_bitlen = min_bitlen;
while (max_traversed_nodes > hashmap::get_size(hash_bitlen) * max_fill_rate) {
  hash_bitlen += 1;
}
RAFT_EXPECTS(hash_bitlen <= 25, "hash_bitlen cannot be largen than 25 (32M)");

(cpp/src/neighbors/detail/cagra/search_plan.cuh, lines 285-288 for the MULTI_CTA traversed-node table.)

The bound check runs after the loop, and the loop has no upper bound of its own. hashmap::get_size() is

// cpp/src/neighbors/detail/cagra/hashmap.hpp:23
RAFT_INLINE_FUNCTION uint32_t get_size(const uint32_t bitlen) { return 1U << bitlen; }

1U << bitlen is undefined behaviour once bitlen >= 32 (shift >= width of unsigned int). In practice on x86 the shift count is masked to 5 bits, so get_size(32) wraps to 1, get_size(33) to 2, and so on. hash_bitlen is declared int64_t, so it keeps incrementing.

The result: whenever the requested table would need bitlen >= 32, the loop condition can never become false again and calc_hashmap_params() spins forever on the host. The RAFT_EXPECTS that was supposed to reject the request is never reached. This is a hang, not an allocation failure or a clean error.

Steps/Code to reproduce bug

1. Root cause, standalone , no GPU or cuVS needed:

#include <cstdio>
#include <cstdint>
// verbatim from cpp/src/neighbors/detail/cagra/hashmap.hpp:23
uint32_t get_size(const uint32_t bitlen) { return 1U << bitlen; }

int main() {
  for (uint32_t b = 29; b <= 35; b++) printf("get_size(%2u) = %11u\n", b, get_size(b));

  double   max_fill_rate      = 0.5;
  uint64_t max_traversed_nodes = 1168750000ULL;   // itopk_size ~1.1e9 under MULTI_CTA
  int64_t  hash_bitlen        = 11;
  for (int guard = 0; guard < 80; guard++) {
    if (!(max_traversed_nodes > get_size(hash_bitlen) * max_fill_rate)) {
      printf("loop TERMINATED at hash_bitlen=%ld\n", (long)hash_bitlen);
      return 0;
    }
    hash_bitlen += 1;
  }
  printf("loop DID NOT TERMINATE (hash_bitlen=%ld and climbing)\n", (long)hash_bitlen);
}

$ g++ -O0 -o getsize_wrap getsize_wrap.cpp && ./getsize_wrap
get_size(29) =   536870912
get_size(30) =  1073741824
get_size(31) =  2147483648
get_size(32) =           1     <-- wraps
get_size(33) =           2
get_size(34) =           4
get_size(35) =           8
loop DID NOT TERMINATE (hash_bitlen=91 and climbing)

2. End to end, through cuvs-lucene:

A single-query AUTO search (which resolves to MULTI_CTA) over a 200-vector, 32-dim index, varying only itopk_size:

// cuvs-lucene; single segment, 200 vectors x 32 dims. Only itopk_size varies.
Codec codec = TestUtil.alwaysKnnVectorsFormat(new CuVS2510GPUVectorsFormat());
float[][] dataset = generateDataset(random(), 200, 32);
try (Directory dir = newDirectory()) {
  try (IndexWriter w = new IndexWriter(dir, new IndexWriterConfig().setCodec(codec))) {
    for (float[] v : dataset) {
      Document d = new Document();
      d.add(new KnnFloatVectorField("vector", v, EUCLIDEAN));
      w.addDocument(d);
    }
  }
  try (DirectoryReader reader = DirectoryReader.open(dir)) {
    IndexSearcher searcher = new IndexSearcher(reader);
    int k = 5;
    int iTopK = 1_100_000_000;   // 1_000_000_000 errors cleanly; 1_100_000_000 hangs
    searcher.search(
        new GPUKnnFloatVectorQuery(
            "vector", dataset[0], k, /*filter=*/ null, iTopK, /*searchWidth=*/ 8,
            /*threadBlockSize=*/ 0, /*maxIterations=*/ 0, CagraSearchParams.SearchAlgo.AUTO),
        k);
  }
}

itopk_size	predicted max_traversed_nodes	vs 2^30	observed
500,000,000	531,250,000	under	clean RAFT_EXPECTS failure at search_plan.cuh:288, 77 ms
1,000,000,000	1,062,500,000	under	clean RAFT_EXPECTS failure, 20 ms
1,100,000,000	1,168,750,000	over	hangs, no error, still running at a 60 s timeout
2,147,483,647	2,281,701,376	over	hangs, no error

The transition sits exactly where the wrap predicts. max_traversed_nodes = max(search_width, ceildiv(itopk_size, 32)) * max(32, max_iterations); the loop can still terminate while the required bitlen <= 31, i.e. while max_traversed_nodes <= 2^30, and hangs above it.

The stuck thread stays RUNNABLE inside cuvsCagraSearchMultiPartition and is not recoverable by the caller's timeout:

1) Thread[id=107, ..., state=RUNNABLE, ...]
     at com.nvidia.cuvs.internal.panama.headers_h.cuvsCagraSearchMultiPartition(headers_h.java:27697)
     at com.nvidia.cuvs.internal.MultiPartitionCagraSearchImpl.search(MultiPartitionCagraSearchImpl.java:185)

Expected behavior

An itopk_size that requires a hash table beyond the supported size should be rejected with the existing RAFT_EXPECTS error, exactly as it already is for the bitlen 26-31 range. It should never hang.

Suggested direction

Bound the loop rather than only checking afterwards, e.g. stop at the documented maximum and fail there:

while (hash_bitlen <= 25 && max_traversed_nodes > hashmap::get_size(hash_bitlen) * max_fill_rate) {
  hash_bitlen += 1;
}
RAFT_EXPECTS(hash_bitlen <= 25, "...");

Making get_size() safe for bitlen >= 32 (returning uint64_t, or asserting on the input) would also remove the undefined behaviour, though the loop still needs its own bound to fail fast.

Worth noting the same shape appears in the other sizing loops in calc_hashmap_params() (lines 270, 303, 343): each increments the bitlen unbounded and checks the limit only afterwards. Line 285 is the one confirmed here. Lines 303 and 343 size from user-controlled itopk_size/search_width, so they look reachable the same way for the non-MULTI_CTA algorithms, though I have not reproduced those. Line 270 sizes from graph_degree only, so in practice it stays far below the wrap. Probably worth fixing together.

Environment details (please complete the following information):

• Environment location: Bare-metal
• Method of cuVS install: from source, VERSION 26.10.00
• GPU: NVIDIA RTX PRO 6000 Blackwell Server Edition

Additional context

Found while adding parameter-boundary validation to cuvs-lucene (#2516). Because the correct upper bound depends on the resolved algorithm, max_iterations, graph degree and dataset size, the Java layer does not try to derive it; it relies on native CAGRA rejecting unsupported combinations, which works for the bitlen 26-31 range but hangs above it.

Thanks to @dantegd for pointing at calc_hashmap_params() and the 1U << bitlen shift range as the likely cause , this issue confirms that diagnosis and pins the threshold.