HNSW Insert Performance Analysis

This page explains why HNSW index construction is expensive, where the time goes, and which levers (configuration and engine-level) affect the insert-throughput vs. recall trade-off.

Versions

Written against core engine 2.0.3. The Python-facing knobs below come from the Python SDK (pure-Python ctypes SDK 0.5.9) and the native engine package (PyO3 2.0.3).

Benchmark numbers are environment-specific

Absolute throughput figures (vectors/second) depend heavily on dimension, hardware (SIMD width, core count), batch size, and whether vectors are normalized at ingest. Treat any single number on this page as illustrative of a trend, not a guaranteed result, and re-measure on your own hardware before drawing conclusions. The relative ordering (higher ef_construction → slower inserts, better recall) is the durable takeaway.

Problem statement

HNSW index construction (inserting vectors) is far more expensive than HNSW search. On the same machine, building an index can be one to two orders of magnitude slower per operation than querying it. When SochDB insert throughput is compared against a speed-optimized vector store, the gap is almost entirely explained by the graph-quality work done at insert time, not by FFI or storage overhead.

Root cause: RNG neighbor selection

Where the time goes

End-to-end profiling of a single-threaded build (see Profiling) shows the overwhelming majority of insert time inside the neighbor-selection heuristic, not in quantization, the hash map, or the FFI boundary:

╔════════════════════════════════════════════════════════════════════════════╗
║                        Time breakdown (illustrative)                       ║
╠════════════════════════════════════════════════════════════════════════════╣
║ Neighbor Selection (RNG heuristic) │ ~80% │ ← MAIN BOTTLENECK              ║
║ Add Connections                    │ ~15% │                                ║
║ Search Layer (candidate gather)    │  ~4% │                                ║
║ Quantization                       │ <1%  │                                ║
║ Map Insert                         │ <1%  │                                ║
║ FFI / Python Overhead              │ <1%  │                                ║
╚════════════════════════════════════════════════════════════════════════════╝

The dominant cost is the RNG (Relative Neighborhood Graph) neighbor-selection heuristic that HNSW uses to keep the graph well-connected and diverse.

Why it is expensive

For every inserted vector, HNSW does roughly the following:

1. Gather candidates: a layer search returns about ef_construction candidate neighbors.
2. Prune with the RNG heuristic: for each candidate, check whether it is "shadowed" by a neighbor already selected — i.e., whether an already-chosen neighbor is closer to the candidate than the new node is.
3. Distance per check: each shadow check is a full distance computation across every dimension (for the default Cosine metric, a dot product plus two norms).

The work scales roughly as:

O(N × ef_construction × max_connections × dimension)

For a 1,000-vector, 768-dimensional build at the current defaults (M = 32, ef_construction = 256) this is on the order of millions of full-dimension distance calculations — which is why the heuristic dominates the profile.

Current HNSW defaults (core 2.0.3)

HnswConfig::default() ships with M = 32, M0 = 64, ef_construction = 256, ef_search = 500, metric Cosine, precision F32. These are higher than older releases (which used M = 16 / ef_construction = 200): M = 32 is the recall sweet spot that "clears 95% out of the box," and ef_construction = 256 was raised to handle hard, high-dimensional embeddings. The trade-off is that the richer build does more neighbor-selection work per insert. See the Architecture reference for the full struct.

The quality vs. speed trade-off

ef_construction is the primary insert-time lever. Lowering it gathers fewer candidates, so the RNG heuristic does proportionally less work — at the cost of a sparser, lower-recall graph.

ef_construction	Relative insert cost	Recall (qualitative)
50	Lowest	Reduced
100	Low	Good
200	Higher	High
256 (default)	Highest	Best (95%+ target)

caution

The exact throughput multiplier between rows is hardware- and dimension-dependent. The relationship is monotonic — fewer candidates means faster inserts and lower recall — but do not quote a fixed "Nx faster" ratio without measuring it yourself.

Tuning ef_construction

If you are ingest-bound and can tolerate slightly lower recall, lower ef_construction on the index you build. With the pure-Python SDK (v0.5.9), HNSW parameters are configured when you create a vector-backed collection/index; with the native engine package (HnswIndex, PyO3 2.0.3) they are passed via the index config. In both cases the knob is the same value documented above.

For most production embedding workloads, leaving ef_construction at the default and ingesting in parallel batches (next section) is the better lever than trimming graph quality.

Engine-level optimizations (shipped in 2.0.x)

Several optimizations that earlier internal notes listed as "future work" are now part of the core engine. They attack the RNG hot path directly:

• Staged parallel construction. The staged builder (hnsw_staged.rs, "Waves + Deferred Backedges") builds in three phases: a sequential scaffold, parallel insertion waves where back-edges are deferred to thread-local buffers, and a final parallel back-edge consolidation. This parallelizes the neighbor-selection work that single-threaded builds serialize.
• SIMD distance kernels. Distance computations use SIMD (simd_distance.rs); for small datasets the search path uses a parallel SIMD flat scan instead of the graph, which is both exact and faster below a dimension-aware crossover (≤128D: 10,000 vectors, ≤384D: 4,000, otherwise 1,000).
• Quantization. Precision supports F32, F16, and BF16 (the half crate), halving bytes-per-element for F16/BF16. Product Quantization is also available (enable_product_quantization, default off; intended for large, high-dimensional sets). Quantization mainly reduces memory bandwidth and footprint rather than RNG compute, but it helps overall throughput on memory-bound builds.
• Adaptive search ef (search-side, not build-side). AdaptiveSearchConfig binary-searches the minimum ef_search that meets a target recall (default target_recall = 0.95, min_ef = 10, max_ef = 500, 100 calibration queries). This tunes query cost to a recall target; it does not change ef_construction.

No "adaptive ef_construction"

The engine adapts ef_search at query time via AdaptiveSearchConfig. There is no auto-tuning of ef_construction at build time — choose it explicitly for your quality/throughput target.

Recall reference points

These are the recall numbers asserted in the core HNSW source (deep-1M dataset, recall@10). They depend on the dataset and parameters and are reproduced here as calibration points, not guarantees:

• M = 16 / M0 = 32: recall@10 ≈ 0.967
• M = 32 (default): recall@10 ≈ 0.988
• M = 48: recall@10 ≈ 0.990
• A 1M build that skips the optional exact layer-0 rebuild completed in ~195s at recall@10 ≈ 0.968.

The default M = 32 is chosen as the point that clears the 95% recall bar without paying for the marginal gains of M = 48.

Practical guidance

• Ingest-bound and recall-tolerant? Lower ef_construction (e.g., 100) and/or use F16/BF16 precision.
• Recall-critical? Keep the defaults; recover throughput by building in parallel batches rather than by lowering graph quality.
• Small collections? You may be below the flat-scan threshold, in which case search is already an exact SIMD scan and HNSW-specific tuning has little effect.
• Always re-measure on your target hardware and dimension before committing to a configuration — the right point on the speed/recall curve is workload-specific.

Conclusion

The cost of building an HNSW index is algorithmic: it is the price of the RNG neighbor-selection heuristic that produces a high-recall graph. SochDB's defaults deliberately favor recall (M = 32, ef_construction = 256). When you need more insert throughput, you can either move down the quality/speed curve by lowering ef_construction, or — preferably — exploit the engine's parallel staged build, SIMD kernels, and quantization to get more throughput at the same recall.