[BUG] CAGRA may miss exact self-match in IP self-query

[marcelo-cjl]

Describe the bug

Hi cuVS team, thanks for taking a look.

I'm seeing cuvs.neighbors.cagra miss exact self-matches in a small inner-product self-query repro. I'm not sure whether this is expected for this CAGRA search configuration, but it is surprising for downstream usage because the exact same vector is present in the indexed dataset.

With normalized vectors, querying xb[i] against an index built from xb has an exact self score close to 1.0. In the repro below, some queries return a different vector with score around 0.16-0.21, and the self vector is not present in the returned top-k.

Steps/Code to reproduce bug

import numpy as np
import cupy as cp
from cuvs.neighbors import cagra

N = 50_000
D = 384
Q = 512
K = 10

np.random.seed(0)
xb_h = np.random.randn(N, D).astype(np.float32)
xb_h /= np.linalg.norm(xb_h, axis=1, keepdims=True)
xb = cp.asarray(xb_h)

index = cagra.build(
    cagra.IndexParams(
        metric="inner_product",
        intermediate_graph_degree=64,
        graph_degree=32,
        build_algo="ivf_pq",
    ),
    xb,
)

dist, ind = cagra.search(
    cagra.SearchParams(
        itopk_size=64,
        search_width=1,
    ),
    index,
    xb[:Q],
    K,
)

dist_h = cp.asnumpy(dist)
ind_h = cp.asnumpy(ind)

expected = np.arange(Q)
bad = np.flatnonzero(ind_h[:, 0] != expected)
print(f"self_top1_count={Q - bad.size}/{Q}")
print(f"first_bad_queries={bad[:10].tolist()}")

for q in bad[:5]:
    top_id = int(ind_h[q, 0])
    returned_score = float(dist_h[q, 0])
    manual_returned_score = float(np.dot(xb_h[q], xb_h[top_id]))
    manual_self_score = float(np.dot(xb_h[q], xb_h[q]))
    print(
        {
            "query": int(q),
            "top_id": top_id,
            "returned_score": returned_score,
            "manual_returned_score": manual_returned_score,
            "manual_self_score": manual_self_score,
        }
    )

Observed output on my machine:

self_top1_count=488/512
first_bad_queries=[3, 27, 38, 68, 135, 138, 144, 182, 206, 238]
{'query': 3, 'top_id': 15297, 'returned_score': 0.18928107619285583, 'manual_returned_score': 0.18928107619285583, 'manual_self_score': 1.0}
{'query': 27, 'top_id': 34697, 'returned_score': 0.210464745759964, 'manual_returned_score': 0.210464745759964, 'manual_self_score': 0.9999999403953552}
{'query': 38, 'top_id': 6944, 'returned_score': 0.16181255877017975, 'manual_returned_score': 0.16181255877017975, 'manual_self_score': 0.9999999403953552}

I also observed the same kind of miss with a smaller row count, for example N=12_000 produced self_top1_count=511/512 with the same script shape.

Expected behavior

Expected the exact self vector to be returned for these self-queries, with an inner-product score close to 1.0.

If this is expected behavior for these CAGRA parameters, any guidance on the recommended build/search settings for this pattern would be appreciated.

Environment details (please complete the following information):

• Environment location: bare-metal
• Method of cuVS install: PyPI wheel
• cuVS version: 25.06.01
• CuPy version: 14.0.1
• GPU: NVIDIA L4
• Driver: 560.35.05
• CUDA runtime reported by nvidia-smi: 12.6

Additional context

This came up while investigating a downstream Milvus GPU_CAGRA report: milvus-io/milvus#49864

[cjnolet]

Hi Marcelo,

It looks like you are using quite an old version of cuVS (unless maybe that was a typo). The version you've referenced is over a year old.

Can you please try with the most up to date version and let us know if this issue still reproduces? Then we can triage on our end and look at a potential fix.

[premal]

Tested on cuVS 26.06 (source build, release/26.06 branch, commit 4addf4e6). Also tested pip cuvs==26.02.

Reproducer: C++ test at N=500K, INT8, dim=384, unit-normalized vectors, 512 self-queries — built and run directly on the GPU (NVIDIA L40S, CUDA 12.x).

We also extended AnnCagraTest (from ann_cagra.cuh) to run at N=50K with dim=384, k=10, itopk=256. All 4 configurations failed with recall well below the 99% threshold:

Builder	Metric	Recall
IVF_PQ	L2	34.1%
IVF_PQ	InnerProduct	28.7%
NN_DESCENT	L2	48.2%
NN_DESCENT	InnerProduct	32.4%

[premal]

Investigation Update: CAGRA Recall Degradation at Scale — num_random_samplings is the Key Lever

We (Me and Claude Code) did a deep investigation into CAGRA search recall across scales from 50K to 20M, motivated by this issue and the downstream milvus-io/milvus#49864. Here's what we found.

Summary

CAGRA search recall drops to ~60% at N>=100K with default search parameters. The root cause is num_random_samplings=1 (the default), which provides no quality selection for search entry points. Setting num_random_samplings=8 recovers recall to 97-99% across all tested scales up to 10M, with 16-27% QPS overhead.

This is particularly relevant for Milvus/Knowhere users because:

1. Knowhere does not expose num_random_samplings — it's hardcoded to the cuVS default of 1
2. Milvus sealed segments are capped at 1 GB (datacoord.segment.maxSize), which means per-segment vector counts of ~500K-2M for typical embedding dimensions (dim 128-768) — squarely in the range where nrs=1 gives ~60% recall

Test Setup

• GPU: NVIDIA L40S (46 GB VRAM)
• cuVS: 26.2.0
• Data: Gaussian mixture INT8, dim=384, 50 clusters (scaled with N), unit-normalized
• Build: graph_degree=64, intermediate_graph_degree=128, build_algo=IVF_PQ
• Search: itopk_size=256, search_width=4, k=100
• Scales tested: N = 50K, 100K, 500K, 2M, 5M, 10M, 20M

Why Gaussian mixture data? Uniform random vectors have no cluster structure — beam search can't navigate efficiently regardless of parameters (83% recall ceiling). Real production embeddings (e5-small, dim=384) achieve 99.7% recall at N=50K with defaults. Gaussian mixture data sits between these extremes and reveals the scaling behavior that real workloads hit at larger N.

Why nrs=1 Fails at Scale

CAGRA search starts by seeding a candidate pool with random entry points, then runs beam search (greedy graph traversal) to refine them. The search budget is bounded by itopk_size — the maximum number of candidate nodes the beam can hold. The beam works by following graph edges from the current best candidates toward the query, greedily improving the candidate set until convergence or budget exhaustion.

The critical question is: can the beam reach the query's true neighborhood from its starting seeds within the itopk budget?

At small N (50K), the answer is almost always yes. The graph is compact — any random node is only a few hops from any other. The beam can traverse from a random start to the query's neighborhood without exhausting its budget.

At larger N (100K+), the graph becomes proportionally larger but itopk stays fixed. A random seed now has a high probability of landing in a distant cluster. The beam must traverse many hops through the graph to reach the query's cluster, consuming candidate slots along the way. If the seed is far enough away, the beam exhausts its itopk budget during traversal and never reaches the true nearest neighbors. It converges to a local optimum in the wrong region of the graph.

This is the mechanism behind the ~60% recall floor at N>=100K: roughly 60% of queries happen to get a random seed close enough that the beam converges correctly, and ~40% get unlucky seeds that strand the beam in the wrong cluster.

num_random_samplings fixes this by changing the seed selection probability. With nrs=1, each seed slot draws one random node — if it's far from the query, that slot is wasted. With nrs=8, each slot evaluates 8 random nodes and keeps the closest to the query (a best-of-8 selection). If the probability that a single random node is "close enough" for beam convergence is p, then:

• nrs=1: probability of a good seed = p
• nrs=8: probability of a good seed = 1 - (1-p)^8

For example, if p = 0.15 (plausible at N=500K), nrs=1 gives 15% chance per slot, while nrs=8 gives 73%. Across ~512 seed slots, nrs=8 virtually guarantees multiple seeds in the query's neighborhood, giving the beam a viable starting point for convergence.

num_random_samplings Sweep Results

Recall across scales (L2, graph_degree=64, itopk=256):

nrs	N=50K	N=100K	N=500K	N=2M	N=5M	N=10M
1 (default)	99.1%	63.6%	59.7%	59.7%	61.7%	60.4%
4	99.4%	94.3%	96.7%	—	95.7%	95.4%
8	99.3%	98.9%	99.2%	98.6%	97.4%	97.4%
16	99.3%	99.5%	98.7%	98.5%	97.6%	97.5%

InnerProduct follows the same pattern:

nrs	N=100K IP	N=500K IP
1	62.8%	53.7%
8	97.5%	96.8%
16	97.2%	97.5%

nrs=8 consistently recovers recall to 97-99% across 3 orders of magnitude. Returns diminish beyond 8.

Why This Matters for Milvus Segment Sizes

Milvus seals segments at datacoord.segment.maxSize = 1024 MB (1 GB). For typical embedding workloads, per-segment vector counts are:

Embedding dim	Bytes/vector (FP32)	Vectors per 1 GB segment
128	512 B	~2M
384	1,536 B	~650K
768	3,072 B	~325K

These are all in the 100K-2M range — exactly where nrs=1 gives ~60% recall. Every Milvus GPU_CAGRA user with a full segment is hitting this problem today, and they cannot work around it because Knowhere doesn't expose the parameter.

Latency Cost

QPS overhead of nrs=8 vs nrs=1 (batch=1000 queries, L2):

N	nrs=1 QPS	nrs=8 QPS	Overhead	Recall improvement
50K	342K	260K	-24%	+0.2% (already 99%)
500K	210K	163K	-22%	+39.5% (59.7 → 99.2%)
2M	158K	116K	-27%	+38.9% (59.7 → 98.6%)
10M	114K	96K	-16%	+37.0% (60.4 → 97.4%)

The overhead comes from the seeding phase evaluating 8x more random distance computations. At N>=500K, nrs=1 gives unusable recall (~60%) — the 16-27% QPS cost is the price of a working index.

Compounding Issue: Milvus graph_degree=32 Default

Milvus overrides the cuVS/Knowhere default of graph_degree=64 with graph_degree=32 in its autoindex config (autoindex_param_cuda.go:26):

DefaultValue: `{"intermediate_graph_degree":64, "graph_degree": 32, ...}`

This caps recall further. Side-by-side at N=10M:

nrs	graph_degree=64 (cuVS default)	graph_degree=32 (Milvus default)
1	60.4%	49.3%
8	97.4%	93.1%
32	97.5%	93.6%

With graph_degree=32, recall plateaus at ~93% even with nrs=32. The sparser graph doesn't have enough edges to navigate accurately at scale. So Milvus users are getting 49% recall in the worst case (both defaults wrong) vs 97% with both fixed.

N=20M: Second Bottleneck (itopk_size)

At N=20M, nrs=8 can no longer recover recall:

nrs	N=10M	N=20M
1	60.4%	37.6%
8	97.4%	60.4%
32	97.5%	60.5%

itopk=256 becomes the hard limit — 256 candidate slots is 0.0013% coverage at 20M, insufficient for beam convergence. This is a different bottleneck from the seed quality issue; it requires increasing itopk_size proportionally. For most Milvus deployments this won't matter (segments top out at ~2M vectors for typical dimensions), but very low-dimensional or INT8 data could push segment sizes higher.

IVF-Seeded Entry Points

We also tested passing IVF-PQ coarse search results as directed seeds (using the seed_ptr infrastructure):

Seeds	N=500K	N=2M	N=10M	N=20M
Random (nrs=1)	59.7%	59.7%	60.3%	37.6%
IVF-PQ (n=1)	61.2%	61.0%	97.3%	60.6%
Random (nrs=8)	99.2%	98.6%	97.4%	60.4%

IVF seeds only become competitive at N=10M (crossover with nrs=8). At smaller scales, nrs=8 is simpler and more effective. Both hit the same itopk ceiling at 20M.

What We Ruled Out

1. Graph pruning quality: Post-prune recall is consistently >= pre-prune. The CAGRA graph is well-constructed.
2. search_width: Marginal improvement (+3-5%) at any scale. Not the bottleneck.
3. IVF-PQ build sub-parameters (n_lists, n_probes, pq_dim): No effect on the miss pattern.
4. INT8 vs FP32: Identical recall. Quantization is not a factor.
5. Build algorithm: IVF_PQ and NN_DESCENT produce equivalent graphs for this analysis.

Questions for cuVS Maintainers

1. Should the default num_random_samplings be higher? The current default of 1 gives usable recall only at N<100K. A default of 8 would fix the common case with modest overhead. Is there a reason the default was set to 1?

2. Is there an intended way to auto-tune num_random_samplings based on dataset size? The relationship appears to be: as N grows, you need more random samples to reliably land near the query's neighborhood. Could cuVS compute a reasonable default from the dataset size?

3. Is there existing work on adaptive itopk_size? At N>=20M, itopk=256 becomes the ceiling regardless of seed strategy. For very large datasets, automatically scaling itopk with N would help.

Proposed Fixes (Downstream)

Knowhere (PR ready):

• Add num_random_samplings to the CAGRA search config struct
• Wire it through to cuVS search_params (currently missing from the params builder at cuvs_knowhere_index.cuh:337-350)
• Default to 1 (inheriting cuVS default), but allows Milvus users to set it

Milvus:

• Expose num_random_samplings in GPU_CAGRA search params
• Consider changing graph_degree default from 32 to 64 (matching cuVS/Knowhere)

Relationship to the Original Issue

The original report (self-match misses at N=50K with graph_degree=32, itopk=64) is a symptom of the same underlying problem. With those parameters:

• graph_degree=32: fewer graph edges = lower recall ceiling
• itopk=64: very small candidate pool
• nrs=1: no seed quality selection

The self-match misses are the most visible manifestation — the search beam starts far from the query and can't reach the exact match within budget. Increasing num_random_samplings would reduce these misses significantly.

@cjnolet @aamijar Please verify these findings and let me know if I can test anything else

[marcelo-cjl]

I will add support for these query parameters in Knowhere as soon as possible.

[jdel12]

Adding to this issue, I was running a quick benchmark for something tangentially related and stumbled onto this.

My findings make it look like CAGRA's nn_descent graph builder silently produces low recall at specific corpus sizes. When N % extended_graph_degree == 0, the initial random graph has degenerate symmetry that prevents convergence at normal iteration counts. Recall drops from 0.99 to as low as 0.17, deterministically, for any dataset.

This is the potential root cause behind #204 and #2102. PR #819 seem to fix it but has been open for 14 months.

Minimal reproducer

import cupy as cp
from cuvs.neighbors import cagra

data = cp.random.randn(54400, 128, dtype=cp.float32)  # N%160==0 → FAIL
params = cagra.IndexParams(
    graph_degree=34, intermediate_graph_degree=100,
    nn_descent_niter=20, build_algo="nn_descent")
index = cagra.build(params, data)
# recall ~0.40. Change 54400 → 54401: recall jumps to 0.996.

Tested on cuVS 26.06.00 — bug is present in the latest release.

Potential root cause

The bug is in GnndGraph::init_random_graph() in cpp/src/neighbors/detail/nn_descent.cuh. The function assigns initial random neighbors by indexing into a pre-shuffled sequence (rand_seq):

// nn_descent.cuh, GnndGraph::init_random_graph()
for (size_t i = 0; i < nrow; i++) {
  size_t base_idx         = i * node_degree + seg_idx * segment_size;
  auto h_neighbor_list    = h_graph + base_idx;
  auto h_dist_list        = h_dists.data_handle() + base_idx;
  size_t idx              = base_idx;  // ← BUG: periodic access into rand_seq
  size_t self_in_this_seg = 0;
  for (size_t j = 0; j < static_cast<size_t>(segment_size); j++) {
    Index_t id = rand_seq[idx % rand_seq.size()] * num_segments + seg_idx;
    // ...
    idx++;
  }
}

idx starts at base_idx (i * node_degree + seg_idx * segment_size) and walks forward through rand_seq. Because base_idx grows linearly with i by stride node_degree, the access pattern into rand_seq is periodic. When gcd(node_degree, rand_seq.size()) is large — which happens exactly when N % extended_graph_degree == 0 — groups of nodes receive identical initial neighbors. This creates symmetric partition boundaries across the CUDA thread grid. The core local_join_kernel_wmma then performs redundant neighbor comparisons across these partitions and early-exits without producing graph updates. The graph barely improves across iterations.

Three hard-coded constants interact to produce extended_graph_degree:

Constant	Location	Value
DEGREE_ON_DEVICE	nn_descent_gnnd.hpp:24	32
NUM_SAMPLES	nn_descent.cuh:201	32
Extension formula	nn_descent_gnnd.hpp:307-310	roundUp32(intermediate_graph_degree * 1.3)

Common parameter choices (e.g. intermediate_graph_degree=100 → ext=160, or intermediate_graph_degree=123 → ext=160 as Elasticsearch uses) hit the bug at round corpus sizes.

Evidence Log

1. Corpus size survey (63 sizes, 100-vector intervals)

Tested at N from 54,000 to 60,200 with graph_degree=34, intermediate_graph_degree=100, niter=20 on 1024d cosine embeddings:

n % 160 == 0:      recall ~0.40 (catastrophic)
n % 160 == 80:     recall ~0.60 (severe)
n % 160 == 40/120: recall ~0.96 (mildly degraded)
n % 160 == other:  recall ~0.997 (normal)

The period 160 matches extended_graph_degree exactly. The failure has multiple severity levels depending on gcd(N, ext).

2. +/−1 vector boundaries (razor-sharp)

Binary search at partition boundaries shows single-vector precision:

54400: 0.40 recall  →  54401: 0.996   (1 vector difference)
55995: 0.998        →  55996: 0.41
56000: 0.41         →  56001: 0.997
59900: 0.40         →  59901: 0.997

3. Data-independent and deterministic

Five random subsets at N=54,400: 0.406, 0.387, 0.409, 0.402, 0.393 — all fail.
Three runs on same data: 0.4000, 0.4015, 0.3995. Same size always fails; content doesn't matter.

4. Graph-degree independent

At N=54,400 with inter=100, niter=20:

graph_degree=12:  recall=0.388
graph_degree=34:  recall=0.414
graph_degree=48:  recall=0.425
graph_degree=64:  recall=0.429

All fail. The bug is in the extended_graph_degree calculation, not the ratio between graph_degree and ext.

5. Convergence analysis (niter 1–100)

Same data, same params, only corpus size differs by 401 vectors:

niter     aligned (N=54,400)     non-aligned (N=54,801)
    1          0.209                  0.723
    2          0.211                  0.930
   20          0.366                  0.961          ← default niter
   50          0.739                  0.973
   75          0.971                  0.975          ← aligned finally converges
  100          0.977                  0.975

Iterations to 0.90 recall: non-aligned needs 2, aligned needs 75 (37.5×). The graph topology IS reachable — convergence is just starved by degenerate update patterns at normal iteration counts.

6. Kernel profiling (ncu)

local_join_kernel_wmma at N=54,400 vs N=54,401 (gd=34, inter=100, niter=20):

                     Aligned       Non-aligned
Kernel launches:     20            20
Avg duration:        4,244 µs      16,696 µs
Total (20 iters):   84,870 µs     333,910 µs
SM throughput:       34.6%         39.3%

The aligned case runs 3.9× faster but produces 0.37 recall vs 0.96. Same iteration count, same kernel launches — each launch does far less useful work because symmetric partitions cause degenerate neighbor comparisons that early-exit. Build speed is a misleading quality signal.

7. CUPTI cross-validation

Independently confirmed the ncu findings using a home cooked BPF-based GPU observability tool.

                        Aligned (N=54,400)    Non-aligned (N=54,401)    Ratio
Total kernel launches:         164                    164              1.0x
Total GPU time:            118.5 ms               339.2 ms            2.86x
Avg kernel duration:         722 µs               2,068 µs            2.86x
Memory operations:             262                    262              1.0x
Memory transferred:        871.7 MB               871.7 MB            1.0x
Sync events:                    94                     94              1.0x

Identical pipeline structure. Identical memory transfer (byte-for-byte, 188 copy ops, 38 allocs, 36 frees). The entire delta is in kernel computation. The full 164-kernel pipeline runs 2.86× faster in the aligned case — diluted from the 3.9× kernel-specific ratio because setup, sort, prune, and merge kernels run at the same speed regardless of alignment.

Duration histograms show bimodal distribution: aligned heavy kernels peak at 512µs–4ms (early-exit), non-aligned at 8–32ms (productive work).

8. ES JVM kernel traces

GPU kernel events captured directly from the ES 9.4.1 JVM process during GPU HNSW builds via the ES Docker container:

Process: /usr/share/elasticsearch/jdk/bin/java
Container: es-cuvs-traced (Docker, GPU 0, trial license)

                        Aligned (N=54,400)    Non-aligned (N=54,401)
Total kernel launches:         114                    114
local_join_kernel:              36                     36
  grid_dim:             (54400,1,1)            (54401,1,1)
add_rev_edges_kernel:           72                     72
kern_prune:                      3                      3
kern_sort:                       3                      3
preprocess_data_kernel:          3                      3
kern_make_rev_graph:           102                    102

Identical pipeline structure confirms the bug is purely in local_join_kernel's convergence behavior — same kernel count, same grid dims (N in the first dimension).

ES uses 36 nn_descent iterations (36 local_join_kernel launches), not the 30 predicted by its own formula (5 + ef_construction / 16 = 30). The extra iterations partially mitigate but don't fix the bug.

9. All ext values fail at scale (200K–1M)

Initial testing at 40K–60K suggested only ext=160 was affected. Testing at 200K–1M proved ALL ext values fail:

SIFT-128 (128d), gd=34, niter=20:

N	ext=128	ext=160	ext=192
200K	0.994	0.322	0.992
400K	0.992	0.305	0.993
600K	0.989	0.320	0.970
800K	0.825	0.317	0.992

Cohere-768 (768d), gd=34, niter=20:

N	ext=128	ext=160	ext=192
200K	0.915	0.313	0.933
400K	0.820	0.259	0.939
600K	0.896	0.252	0.689
800K	0.603	0.242	0.934

Higher dimensions make every ext value fail harder and earlier. ext=128 drops to 0.574 at ~1M on Cohere-768. ext=192 fails at 600K. All N±1 controls pass (>0.93).

Clamping to a "safe" ext just shifts the failure to a different corpus size.

10. 1024d cross-validation

At 1024d (AG News + mxbai-embed-large-v1), N=100,000 aligned vs N=100,001 non-aligned, m=48, ext=160:

nc	Aligned recall	Non-aligned recall	Aligned 1/R@10	Non-aligned 1/R@10
10	0.1652	0.7968	0.804	0.984
100	0.3179	0.9899	0.870	1.000
1000	0.6131	0.9996	0.942	1.000

Recall and aligned 1/R@10 are from the controlled Path B test run (§11). Non-aligned 1/R@10 is from the initial cross-validation run on the same hardware — values are consistent across runs within noise.

At higher dimensionality the bug degrades distance quality too — 1/Ratio@10 (Dimitropoulos & Mamoulis 2025) drops to 0.80 at nc=10, meaning the returned neighbors are measurably farther from the true nearest neighbors, not just reordered.

11. Patched build validation (end-to-end through Elasticsearch)

I built a patched libcuvs.so from the v25.12.00 source with the fix below, swapped it into an ES 9.4.1 GPU container, and re-ran the 1024d test. An unpatched instance ran simultaneously as a control.

Aligned (N=100,000, N%160=0):

nc	Unpatched recall	Patched recall	Unpatched 1/R@10	Patched 1/R@10
10	0.1652	0.7960	0.804	0.984
50	0.2614	0.9699	0.849	0.999
100	0.3179	0.9903	0.870	1.000
200	0.3948	0.9966	0.893	1.000
500	0.5199	0.9991	0.922	1.000
1000	0.6131	0.9997	0.942	1.000

Non-aligned control (N=100,001) — confirms no regression:

nc	Unpatched recall	Patched recall
10	0.7968	0.7931
100	0.9899	0.9908
1000	0.9996	0.9997

Patched aligned (0.796) matches non-aligned (0.793) at nc=10. Bug eliminated. No regression.

12. ivf_pq is unaffected

Same params, same data:

nn_descent: 0.40–0.99 (size-dependent)
ivf_pq:     0.987 (stable at all sizes)

The bug is specific to nn_descent's init_random_graph(), not CAGRA's graph format or search.

Fix

Option A (recommended): Fix init_random_graph() index calculation

In GnndGraph::init_random_graph() (nn_descent.cuh), replace the sequential starting index with a multiplicative hash:

// Before:
  size_t idx              = base_idx;

// After:
  size_t idx              = static_cast<size_t>(i) * 2654435761u;

Knuth's golden-ratio hash spreads starting positions uniformly across rand_seq, breaking the periodicity for all corpus sizes and all ext values. The constant is coprime to all practical sizes.

I built a patched libcuvs.so from v25.12.00 with this change, swapped it into an ES 9.4.1 container, and validated end-to-end at 1024d (see evidence §11). The fix eliminates the alignment gap with no regression.

This is the same approach as PR #819, which has been open since April 2025.

Option B: Phantom node padding

When N % ext == 0, pad the working set by one phantom (zero-filled) vector:

bool needs_phantom = (num_rows % extended_graph_degree == 0);
size_t alloc_rows  = needs_phantom ? num_rows + 1 : num_rows;

Verified to restore recall from 0.30–0.40 to 0.94–0.998 across SIFT-128 and Cohere-768 at 55K and 200K. More invasive (touches data copy paths in GNND::build()).

Environment

• cuVS 26.06.00 (standalone) / 25.12.0 (bundled in ES 9.4.1)
• CUDA 12.8–13.0, Driver 580.159.03
• GPU: RTX 4060 Ti 16GB
• Datasets: SIFT-128, Cohere embed-english-v2.0 (768d), AG News + mxbai-embed-large-v1 (1024d)

Related

• [BUG] NN Descent has low recall for large datasets #204 — low recall for large datasets (this is the root cause)
• [BUG] CAGRA may miss exact self-match in IP self-query #2102 — recall degradation at scale (this is a contributing root cause)
• [BUG] NN Descent iteration terminating early for small dataset and specific data dimension #184 — early termination
• [BUG] cuVS Nearest Neighbors recall lower than expected for some datasets #1370 — lower recall than CPU pynndescent
• [BUG] Low recall with CAGRA when sparsity or dimensionality is high #761 — low recall with high sparsity/dimensionality
• PR [BUG] Fix CAGRA search recall with a graph built by NN Descent #819 — the fix (open 14 months, blocked on unrelated int8 test failure)

[premal]

@marcelo-cjl IMO, adding tuning params to make CAGRA work is a losing battle. ie: nrs and itopk need to be scaled up linearly (or maybe even exponentially) based on the size of the graph. And by scaling those values up, there is more work to do and hence it degrades the QPS even though it helps with the recall.

In my understanding, the CAGRA code has fundamental flaws and those need to be resolved.

[cjnolet]

@premal

Your assumption here is not correct- the parameters do not scale with dataset size. The optimal choice of graph degree, itopk (, etc...) have more to do with intrinsic dimensionality and choice of k. If graph degree and itopk scaled with number of vectors in the index then neither of these graph algorithms would work (and it would be a sign that they aren't capturing any sort of local structure).

Please do let us know how we can generate your test dataset here so we can help sort through this. Ideally we can use a real world dataset.

@marcelo-cjl @premal we have been digging into this issue and shoukd have a response soon. @jdel12 we believe your issue is not the same as what @marcelo-cjl has created in the issue. We would like to continue helping with both discussions, but might want to consider opening up another issue for yours.

@marcelo-cjl if you have number of random seeds set to 1, then that's a lot lower than what we generally recommend, which is to start around 32 and adjust from there. 1 random seed is just not enough to converge in a reasonable number of iterations. I agree with @premal that we should allow this to be set in Milvus.

cc @anaruse and @enp1s0 who have been investigating this from our side.

[premal]

@cjnolet I was testing CAGRA on milvus and ran into this issue. So, I opened an issue with milvus which prompted @marcelo-cjl to open the issue with cuvs.

Quick summary, I was getting 0 recall on the collection with the CAGRA index while testing with the same data that was ingested in the collection.