[BUG] HDBSCAN connect-components: int32 index overflow in compress_to_bits once row_batch_size * n_components >= 2^31 #3035

Describe the bug

cuML HDBSCAN(min_samples=1) crashes on large inputs with cudaErrorIllegalAddress, which usually surfaces as a std::bad_alloc of a few hundred MB from the next allocation. The fault is in the connect-components step of the MST build.

build_sorted_mst calls connect_knn_graph, which uses a default row batch of 4096 (cpp/src/cluster/detail/mst.cuh:130). cross_component_nn then calls perform_1nn. That function allocates a bool adjacency of row_batch_size x n_components (cpp/src/sparse/neighbors/detail/cross_component_nn.cuh:334) and passes each batch to masked_l2_nn. There it is wrapped as make_device_matrix_view<const bool, int>(adj, m, num_groups) (cpp/src/distance/detail/masked_nn.cuh:264), and compress_to_bits indexes it with int (cpp/src/distance/detail/compress_to_bits.cuh:29, tile indices at 43-55). The mask lambda in perform_1nn also splits the linear index with raft::util::FastIntDiv, which is 32-bit.

With min_samples=1 the first MST pass over the 1-NN graph leaves one component per mutual nearest-neighbour pair. Once 4096 * n_components >= 2^31, that is from 524,288 components, the index wraps and the kernel reads out of bounds. How many rows that takes depends on the data: 0.26 components per row on our text embeddings, 0.17 on the Gaussian data below.

We first hit this on 2,416,283 text embeddings (PCA to 372 dimensions), where the first pass left 629,687 components. A 2,453,658-row input from a different vocabulary had run fine earlier, which made it look data dependent; what matters is the component count. The code is the same in 26.04, 26.10 and on main (54d5767).

Steps/Code to reproduce bug

import cupy as cp
from cuml.cluster import HDBSCAN

N_ROWS = 3_500_000
X = cp.random.RandomState(0).standard_normal((N_ROWS, 16), dtype=cp.float32)
HDBSCAN(min_samples=1, min_cluster_size=2, build_algo="brute_force").fit_predict(X)

About three minutes in, with roughly 40 GB of device memory free:

  File "cuml/cluster/hdbscan/hdbscan.pyx", line 1048, in cuml.cluster.hdbscan.hdbscan.HDBSCAN.fit
  File "cuml/cluster/hdbscan/hdbscan.pyx", line 345, in cuml.cluster.hdbscan.hdbscan._HDBSCANState.init_and_fit
MemoryError: std::bad_alloc: CUDA error (failed to allocate 302912512 bytes) at: /__w/rmm/rmm/cpp/include/rmm/mr/cuda_memory_resource.hpp:51: cudaErrorIllegalAddress an illegal memory access was encountered
CUDA call='cudaEventDestroy(event_)' at file=/pyenv/versions/3.14.3/lib/python3.14/site-packages/libraft/include/raft/core/resource/cuda_event.hpp line=23 failed with an illegal memory access was encountered

The 1-NN graph of this data (cuML NearestNeighbors(n_neighbors=2), weak components with scipy) has 591,627 components, and 4096 x 591,627 = 2,423,304,192. With N_ROWS = 2_500_000 the graph has 419,555 components (4096 x 419,555 = 1,718,497,280 < 2^31) and the same fit completes.

Expected behavior

The fit completes. Either the adjacency view and compress_to_bits take the caller's index type (int64 in HDBSCAN) and the mask lambda uses plain division for it, or perform_1nn / connect_knn_graph caps row_batch_size at INT_MAX / n_components.

Environment details (please complete the following information):

• Environment location: Bare-metal (Ubuntu 24.04.4, Python 3.12.3; NVIDIA RTX PRO 6000 Blackwell Workstation Edition 96 GB, driver 580.159.04, CUDA 13.0 driver API)
• Method of cuVS install: pip wheels, cuml-cu12 / libcuml-cu12 / libcuvs-cu12 26.4.0; 26.10.0 crashes the same way on our 2.4M-row data

Additional context

Our workaround interposes the exported perform_1nn<long, float, MutualReachabilityFixConnectivitiesRedOp<long, float>> with a small preload library. It counts the components, lowers row_batch_size to INT_MAX / n_components when the product would overflow, and calls the original. With it the 2.4M-row fit finishes (78 minutes on the GPU above; only the first connect round needed the cap, 4096 down to 3410). On the synthetic data above it completes as well: the shim saw 591,626 components, lowered the batch from 4096 to 3629, and the fit finished in 1220 s.

Changing the batch size is not neutral, though: the result depends on it because of the core-distance row index, see #3036.