hnsw

A complete from-first-principles C++17 HNSW vector index with reproducible benchmarks, persistence, a bounded concurrent TCP search service, and runtime-selected SIMD distance kernels. Start with the project closeout for the delivered scope, headline results, reproduction path, and remaining limits. The historical gated roadmap is in plan.md, and detailed implementation evidence is in status.md.

The version 1 network byte contract is specified in the wire protocol. The current networking slice also provides a transport-independent query service over an immutable index and a TCP server and reference client. The persistent load and fault harness adds deterministic closed-loop concurrency and local overload, slow-reader, reset, and shutdown exercises. The checked Stage 7 SIFT10K network evidence records raw runs, owned-process lifecycle metadata, derived summaries, a plot, checksums, and a fail-closed relocatable validator. Review-driven repairs add exact command/diagnostic and producer-identity binding, non-regular-file rejection, producer-worktree reproduction, and interruption-safe child cleanup. The networking gate is complete. The final optimization slice adds runtime-selected SIMD distance kernels as described in the performance notes. The checked Stage 8 closeout records scalar versus NEON measurements on the isolated distance loop and the SIFT10K query path. Cache-layout and prefetch experiments are deliberately outside the completed scope. hnsw_server uses a single-threaded nonblocking poll reactor with a bounded connection registry and per-connection frame and response state. Validated SEARCH and BATCH_SEARCH work runs in a bounded worker pool with conservative response-memory reservations. The poll owner enforces frame assembly, idle, request, write-stall, and bounded graceful-drain deadlines. SIGINT and SIGTERM stop admission, drain accepted work, and emit one final shutdown diagnostic; a second lifecycle signal is the operator's immediate escape hatch.

On Unix platforms, serve a validated snapshot and query its dynamic test port with:

./build/hnsw_server --index index.hnsw --bind 127.0.0.1 --port 0
./build/hnsw_client health --host 127.0.0.1 --port PORT
./build/hnsw_client search --host 127.0.0.1 --port PORT \
  --queries queries.fvecs --query-index 0 --k 10 --ef-search 100
./build/hnsw_load run --host 127.0.0.1 --port PORT \
  --queries queries.fvecs --connections 8 --requests 10000

The server prints its actual address and PORT once in readiness JSON. The protocol is cleartext and unauthenticated; loopback is the safe default.

Build and test

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failure

Normal Release builds preserve the toolchain and caller's configuration flags; the project does not overwrite them or inject -march=native. Target-scoped strict floating-point options use the compiler's native spelling. Configuration rejects fast-math, reassociation, and fast-contraction requests in global, standard, and configured custom C++ flag variables.

On a supported Unix compiler/runtime, the focused race check is:

cmake -S . -B build-tsan -DCMAKE_BUILD_TYPE=Debug -DHNSW_ENABLE_TSAN=ON
cmake --build build-tsan --target test_hnsw_tcp test_hnsw_poll_server test_hnsw_search_workers
ctest --test-dir build-tsan -L tsan_focused --output-on-failure

The option performs a compile/link capability probe and fails clearly when ThreadSanitizer is unavailable or combined with ASan/UBSan flags. Fork/exec process tests are intentionally outside the focused TSan label.

SIFT1M dataset

Datasets are intentionally ignored. Place the standard SIFT1M files at:

data/sift/sift_base.fvecs
data/sift/sift_query.fvecs
data/sift/sift_learn.fvecs
data/sift/sift_groundtruth.ivecs

When the original sibling checkout already contains SIFT1M, reuse it without duplicating the files:

mkdir -p data
ln -s ../../HNSW/data/sift data/sift

The legacy hnsw executable runs a small brute-force validation and therefore needs the base, query, and ground-truth files. Persisted-index workflows use hnsw_cli; reproducible sweeps use hnsw_benchmark.

Flat NSW validation

FlatNswIndex::build inserts vectors in node-ID order. Each new node chooses the nearest search candidate whose protected degree has capacity as its parent. If the bounded search finds no such candidate, the immediately preceding node is the deterministic fallback. These parent edges form a protected spanning tree that is never pruned, so every built node remains reachable from entry node 0. For more than two nodes, max_degree must be at least two because a connected simple graph with maximum degree one is mathematically impossible.

Other reciprocal links are selected by bounded graph search. Pruning preserves the tree edges and fills remaining degree slots with the closest (distance, node ID) neighbors; removing an optional edge removes its reciprocal edge as well. Protected links can displace a closer optional link, trading one or more degree slots for the reachability guarantee. This nearest-neighbor policy is the intentionally simple flat-NSW baseline; the diversity heuristic belongs to the hierarchical HNSW stage.

The public search API starts from node 0, requires ef_search to cover the number of results that can actually be returned, and orders distance ties by node ID. Search workspaces can be reused sequentially but not concurrently.

After linking data/sift as above, reproduce the Stage 2 gate with:

./build/nsw_sift_validation \
  data/sift/sift_base.fvecs data/sift/sift_query.fvecs \
  10000 100 16 100 100

The positional parameters after the two paths are base count, query count, maximum degree, efConstruction, and efSearch. The runner builds the index, uses brute-force search on the same base prefix as its oracle, reports recall@10 and approximate-search QPS, and fails unless recall@10 exceeds 90%. Numeric arguments use unsigned decimal notation without signs, whitespace, or leading zeroes.

Hierarchical HNSW search and validation

HnswIndex::search starts at the current maximum-level entry point, descends each upper layer with ef = 1, and runs SEARCH-LAYER at level zero with the caller's ef_search. It returns at most min(k, index size) results ordered by (squared-L2 distance, node ID). For positive k, ef_search must be positive and at least that result count. k = 0 returns immediately; an empty index returns no results without reading the query. Used queries and all computed distances must be finite.

Search workspaces retain scratch allocation across sequential queries. They are not safe to share concurrently, so each concurrent caller needs its own HnswSearchWorkspace. Construct a workspace with HnswSearchOptions{L2Kernel::scalar} to force the portable reference kernel, or use the default auto, which selects NEON on supported AArch64 builds, AVX2 or SSE2 on capable x86 builds, and scalar otherwise. An explicit neon, sse2, or avx2 request succeeds only when that kernel is compiled and available on the current CPU; otherwise it fails without substituting another kernel. Construction, insertion, pruning, exact validation, and snapshot topology always use the scalar reference contract.

Index persistence

Include hnsw_persistence.hpp to save or load an immutable index:

hnsw::save_hnsw_index(index, "index.hnsw");
hnsw::HnswIndex loaded = hnsw::load_hnsw_index("index.hnsw");

The versioned format uses explicit little-endian fixed-width fields, stores IEEE-754 binary32 values without native structs or padding, and protects the header and payload with CRC-64. Loading validates the fixed header and exact file shape, applies configurable HnswLoadLimits, streams checksum validation through a fixed buffer, and only then allocates and decodes the graph. The decode pass rechecks the exact header and CRC-validates every byte it consumes before returning, so an in-place change between passes is not silently accepted. Callers must still serialize in-place writers; CRC is not an authentication mechanism. Format, I/O, and resource failures have separate exception types.

Saving publishes through an exclusively created, basename-independent same-directory temporary file and atomic rename, so a pre-rename failure cannot replace a known-good destination with a partial snapshot. New files use mode 0600; replacements preserve the mode bits of an existing regular file. The file is synchronized before rename, but the parent directory is not yet synchronized for power-loss durability.

See the version 1 index format for the byte layout, compatibility policy, validation rules, and portability limits. Loaded indexes are query-capable and immutable; construction-only protected-edge bookkeeping is not serialized because it is not needed by search.

Snapshot CLI

Build, inspect, and query a deterministic persisted index with:

./build/hnsw_cli build \
  --input data/sift/sift_base.fvecs --index sift10k.hnsw \
  --count 10000 --m 16 --m0 32 --ef-construction 100 --seed 24301

./build/hnsw_cli inspect --index sift10k.hnsw

./build/hnsw_cli query \
  --index sift10k.hnsw --queries data/sift/sift_query.fvecs \
  --query-count 100 --k 10 --ef-search 100 \
  --results sift10k-results.csv

Successful commands emit one stable JSON summary to standard output. Query results can be atomically published as CSV or JSONL; optional .ivecs truth adds conventional exact-ID recall@k. Run ./build/hnsw_cli --help for command help. The complete parsing, timing, resource-limit, output, aliasing, and exit status contract is documented in the snapshot CLI contract. CLI paths must be valid UTF-8 so JSON summaries remain valid on POSIX systems that otherwise permit arbitrary filename bytes.

After linking data/sift, reproduce the Stage 3 gate with:

./build/hnsw_sift_validation \
  data/sift/sift_base.fvecs data/sift/sift_query.fvecs \
  10000 100 16 32 100 100 24301 10

The numeric arguments are base count, query count, upper-layer M, layer-zero M0, efConstruction, efSearch, seed, and k. The runner derives the level scale as 1 / log(M), builds over the requested base prefix, and calculates recall against brute force on that same prefix. Reported latency and QPS include only HNSW query calls; exact-oracle work is outside the timed interval. p50, p95, and p99 use the nearest-rank definition.

On July 15, 2026, the command above reached 0.9940 recall@10 on an Apple M1 Pro with AppleClang 21.0.0.21000101: build 1.927 seconds, 9,011.3 query-only QPS, and 107.9/152.8/170.3 microsecond p50/p95/p99 latency. This is a controlled SIFT10K/100-query gate, not a full SIFT1M benchmark or parameter sweep.

Reproducible benchmark sweeps

hnsw_benchmark emits CSV to standard output by default. Comma-separated sweep values are parsed as canonical positive integers, sorted, deduplicated, and run as a cross product. Every configured M0 must cover every M, every efConstruction must cover every M0, and every efSearch must cover k. --l2-kernel auto|scalar|neon|sse2|avx2 records both requested and selected kernels. auto and scalar are always available; explicit SIMD availability depends on the build architecture, compiler support, CPU features, and x86 OS vector-state support.

This SIFT10K command produces a recall-versus-throughput curve and a separately timed exact brute-force row:

./build/hnsw_benchmark \
  --base data/sift/sift_base.fvecs \
  --queries data/sift/sift_query.fvecs \
  --base-count 10000 --query-count 100 \
  --m 8,16 --m0 32 --ef-construction 64,100,200 \
  --ef-search 10,20,50,100,200 --k 10 \
  --warmup 100 --repetitions 5 --seed 24301 \
  --l2-kernel scalar --exact-baseline --output sift10k-curve.csv

Prefix mode computes exact top-k results against the selected base before any timed query. For a full SIFT1M run, supplied ground truth avoids that setup cost and is deliberately rejected if a base prefix is requested:

./build/hnsw_benchmark \
  --base data/sift/sift_base.fvecs \
  --queries data/sift/sift_query.fvecs \
  --base-count all --query-count all \
  --truth full-sift-groundtruth \
  --groundtruth data/sift/sift_groundtruth.ivecs \
  --m 16 --m0 32 --ef-construction 200 \
  --ef-search 20,50,100,200 --k 10 \
  --warmup 100 --repetitions 3 --seed 24301 \
  --l2-kernel scalar --output sift1m-curve.csv

Dataset I/O and truth generation are outside all measurements. Input copying used to stage an index build is outside build time. A build is performed once per (M, M0, efConstruction) tuple and reused for its efSearch rows. Each row warms a fresh search workspace, then measures every query in stable order for every repetition. Per-query timers cover only the search call; recall and CSV formatting are outside them. query_seconds is the sum of those durations, QPS is measured calls divided by that sum, and latency percentiles use nearest rank over all query/repetition samples. Recall is total top-k set overlap divided by query_count * repetitions * k. The complete recall denominator is overflow-checked during option parsing when the query count is explicit and again immediately after resolving all, before truth generation, index construction, warm-up, or measurement.

logical_index_bytes is a deterministic packed-layout estimate rather than resident memory: float coordinate payload, directed neighbor-ID payload, one maximum-level value per node, one 64-bit offset per adjacency list plus a terminal offset, and entry-point ID/level metadata. It excludes allocator, container-capacity, and temporary workspace overhead. Output files are published only after the complete run by writing and renaming a temporary file. The brute-force row accounts only for its coordinate payload. Schema version 3 also records requested and selected L2 kernels alongside all parameters, counts, seed, repetitions, truth source, compiler, active build configuration, operating system, and processor. cmake_cxx_flags is limited to configured CMAKE_CXX_FLAGS plus the active CMAKE_CXX_FLAGS_<CONFIG> value. It does not claim to reproduce the complete compiler invocation: implicit toolchain flags and directory-, target-, or source-level compile options are outside this field, as are flags generated from target properties such as the selected C++ standard.

Scalar distance microbenchmark

hnsw_distance_benchmark measures the isolated dispatch call over deterministic finite inputs. Vector count controls hot versus larger working sets; generation and allocation finish before warm-up and timing. Fixed iterations are the default, while --iterations auto --target-ms N performs a bounded calibration:

./build/hnsw_distance_benchmark \
  --l2-kernel scalar --dimension 128 --vectors 1024 \
  --warmup 10000 --iterations 100000 --trials 5

./build/hnsw_distance_benchmark \
  --l2-kernel scalar --dimension 128 --vectors 65536 \
  --warmup 10000 --iterations auto --target-ms 250 --trials 5

Each classic-locale CSV row records exact build provenance, requested/selected kernel, working-set shape, elapsed steady-clock time, distance and logical-byte throughput, and an externally printed checksum. It neither reads hardware cycle counters nor subtracts loop overhead. The checked Stage 8 closeout uses this runner and hnsw_benchmark to compare scalar and automatic dispatch on identical local workloads.

The checked-in Stage 4 SIFT1M baseline contains immutable raw CSVs, dataset and raw-artifact checksums, a merged clean CSV, and deterministic SVG plots. It covers all one million base vectors and 10,000 supplied-truth queries for an efSearch curve, paired M/M0 sweep, and efConstruction sweep. Recreate or verify every derived artifact with:

python3 results/stage4-baseline/plot_results.py
python3 results/stage4-baseline/plot_results.py --check

Metadata is written to an escaped, per-configuration generated header instead of being transported through CMake compile-definition lists. This preserves configured backslashes, quotes, escaped semicolons, commas, and CSV-sensitive content. Standard configuration names are canonicalized case-insensitively and deduplicated, so release, RELEASE, and Release select the Release flags once and report Release. Configuration discovery uses explicit empty-string and list-length checks; grammar-valid names that CMake normally interprets as false constants, including 0, OFF, and *-NOTFOUND, remain ordinary names.

The dedicated generated-metadata root contains immutable, content-addressed generations. Each generation has a versioned ownership manifest with its exact configuration, file, directory, and per-file SHA-256 inventory. The generation name is the SHA-256 of that canonical manifest; validation recomputes both the manifest identity and every artifact hash. Each configuration is one ordered group: configuration, header and hash, expectation and hash, then directory; records cannot be separated or reordered. CMake rejects a linked metadata root, validates the complete active generation before changing state, stages the exact replacement bytes, and publishes them with a single active.txt pointer replacement. Only an exact generation-<64 lowercase hex> name can be active; internal staging-* names are never accepted through the active or reuse path. A failed publication leaves the prior generation authoritative and complete. Inactive generations and unrelated root content are retained, so stale resources cannot become active through directory discovery. The CLI integration test independently checks the same grammar, hashes, manifest identity, and actual generation resources.

Configure is a single-writer operation for a build tree. Run only one CMake configure process against a given build directory at a time; cross-process serialization is outside the metadata publisher's contract. Manifest v2 fails closed on earlier unhashed manifests; recreate a pre-v2 build directory once when updating across that schema boundary.

The CLI integration test verifies configuration labels and configured flags. With Ninja installed, exercise Debug and Release from the same multi-config tree with:

cmake -S . -B build-multi -G "Ninja Multi-Config"
cmake --build build-multi --config Debug -j
ctest --test-dir build-multi -C Debug -R test_benchmark_cli --output-on-failure
cmake --build build-multi --config Release -j
ctest --test-dir build-multi -C Release -R test_benchmark_cli --output-on-failure

When Ninja is available, test_benchmark_metadata_recursive also creates a nested lowercase-release build with an escaped-semicolon/quote/backslash/comma flag value, builds the real benchmark, compares its CSV to an independently written raw expectation resource, and removes the nested build on success. It also configures a mixed-case duplicate multi-config list, checks idempotence, producer/consumer configuration-name parity, strict hash and inventory parsing, content-identity mismatch rejection, failed-publication preservation, and a successful multi-configuration reduction. Root and manifest safety checks verify that rejected state cannot change previously published or unrelated content.

Optional hnswlib reference

The controlled comparison runner pins official nmslib/hnswlib v0.9.0 at commit d9b3608c83d83b46c96e25088cb1d729b29dcfe9. Default configure, build, and tests remain offline and do not require hnswlib. Fetch and enable the reference explicitly:

cmake -P cmake/FetchHnswlibReference.cmake
cmake -S . -B build-reference -DCMAKE_BUILD_TYPE=Release \
  -DHNSW_ENABLE_HNSWLIB_REFERENCE=ON \
  -DHNSWLIB_SOURCE_DIR="$PWD/.cache/hnswlib-v0.9.0-d9b3608c83d83b46c96e25088cb1d729b29dcfe9"
cmake --build build-reference -j
ctest --test-dir build-reference --output-on-failure

hnswlib_reference uses the direct C++ API, sequential construction and query, hnswlib squared L2, implicit M0 = 2*M, matched benchmark phases, and a provenance-explicit CSV. See the reference methodology for the pin, measurement boundaries, and fairness limits. The checked full-SIFT1M comparison preserves the raw 14-configuration evidence, derived tables, plots, checksums, run windows, and validation commands. At matched parameters, its headline sweep recorded higher hnswlib recall and higher project raw QPS at every efSearch point; the separately named size fields are not interchangeable memory measurements.