HNSW range_search iterator stuck at ~50% recall due to directed level-0 graph reachability

[foxspy]

Description

HNSW range_search's iterator path has a hard recall ceiling of ~50% on
certain structured datasets, caused by directed reachability of the
level-0 graph — forward BFS from entry_point along out-edges covers only
about half of the nodes, and no parameter tuning (ef, range_search_level,
seed choice) changes this.

Measurements

On the dataset attached to milvus-io/milvus#44854 (15000 vec, 40 dim,
M=128, efConstruction=10000):

ntotal               = 15000
fwd_reach_from_entry = 7695        # iterator reaches ~51% of nodes
bwd_reach_to_entry   = 15000       # reverse BFS covers every node
scc_count            = 7306
largest_scc          = 7695        # only SCC with size > 1
scc_size_eq_1        = 7305        # 7305 singleton SCCs

The level-0 graph decomposes into one SCC of 7695 nodes (containing
entry_point) plus 7305 source-only singletons. Each singleton has
out-edges pointing into the big SCC, but no node in the big SCC has an
out-edge pointing back, so the iterator cannot visit them.

Sampled forward BFS from 20 random seed nodes: min=7695, max=7696 —
the ceiling is invariant to starting seed.

Related

• [Bug]: HNSW + IP range filter: recall ≤ ~0.5 , while unfiltered ≈ 1.0 and IVF_FLAT(filtered)=1.0 milvus-io/milvus#44854 — user-facing report
• fix: check brute-force threshold before iterator path in HNSW RangeSearch #1535 — added BF fallback for range_search when ef >= ntotal * 0.5
• HNSW range_search returns 0 results when ef >= ntotal/2 with empty bitset #1561 — separate latent bug in the BF fallback path

[foxspy]

/assign @marcelo-cjl