HNSW: efConstruction does not scale with corpus size — recall plateaus at 1M vectors regardless of search ef #2180

Priority: P1

Summary

efConstruction defaults to 100 and never scales with corpus size, while the search-side ef auto-scales (AUTO_EF_BASE/AUTO_EF_MAX in HierarchicalNavigableSmallWorld.ts). At 1M vectors this becomes the recall bottleneck: recall@10 drops to 0.935 and cannot be recovered by any amount of search-side ef — the missing neighbours are unreachable in the graph, because the edge-selection candidate list stayed at 100 while the corpus grew 10×.

Found while extending #2125's scaling benchmark to 1M vectors (full data in the PR thread).

Evidence

All runs on benchmarks/hnsw-scale.js (768-dim, int8, calibrated Gaussian-mixture corpus at d(nn)/d(rand) ≈ 0.65 — the harder-contrast regime, matching the corpus the reporter of #2069 measured). Fixed seed, so the A/B graphs below index the identical corpus with identical level assignments.

Recall@10 (raw / candidate-set) across the sweep, ef = auto (pinned at AUTO_EF_MAX 512 from ~13K nodes up):

Ruling out the search side — sweeping ef over the same 1M graph:

Recall plateaus ~0.96 at 4.7× the latency: not an ef ceiling.

Attribution at 1M, ef 512:

efConstruction 200 fully restores 100K-level recall — and the queries get faster at the same ef (3,110 nodes visited vs 3,948; better edges route more directly). Quantization contributes ~1.5 points; construction quality is the dominant term.

Proposed fix

Auto-scale efConstruction with graph size when it is not explicitly configured, mirroring the existing search-side auto-scale — evaluated at insert time from the same node count the search side already resolves. An explicitly configured efConstruction stays authoritative. The cost is build time (1.77× at 1M for efC 200), paid only by tables that actually grow large; small tables see no change.

Caveats

• Evidence is one synthetic corpus (calibrated to the harder-contrast regime); the shape of the conclusion should hold on real embeddings but the constants deserve confirmation there, same as the AUTO_EF_BASE question deferred in Remove linear-in-corpus-size work from HNSW vector search, and honor limit past the candidate list #2125.
• Benchmark harness is in-memory; production build cost also includes store I/O, so the relative build-time increase should be smaller than 1.77×.

Generated by Claude Fable 5.