--- title: "Building a Persistent, Quantized, Deletable HNSW in Rust — No hnsw_rs, No faiss, No BSL" description: "Eight phases (P0–P7) of the in-house, from-scratch persistent PQ-HNSW: Malkov & Yashunin graph, RocksDB persistence under __vidx:, PQ + ADC + two-stage rerank, online deletes with neighbour repair, filtered KNN evaluated during traversal, F32/F16/I8 rerank dial. Apache 2.0 end-to-end, no third-party graph crate." date: 2026-06-04 updated: 2026-06-04 tag: "Engineering" canonical: https://www.heliosdb.com/blog/persistent-quantized-deletable-hnsw-in-rust.html --- # Building a Persistent, Quantized, Deletable HNSW in Rust — No hnsw_rs, No faiss, No BSL The persistent PQ-HNSW path in Nano v3.32 is a from-scratch, in-house implementation. No `hnsw_rs`, no `faiss`, no third-party graph crate. Apache 2.0 end-to-end. Eight phases (P0–P7) over the merge branch `feat/persistent-pq-hnsw`, from design (`87b0497`) to the head-to-head benchmark on main (`8699293`). This is what was in each phase and why we built it ourselves. ## Why in-house Two reasons. **Licensing.** The strongest off-the-shelf Rust vector indexes are BSL or AGPL — fine for an internal tool, a problem for a database you want anyone to host or resell. Apache 2.0 was a hard constraint, which narrowed the options. **Persistence shape.** Most in-RAM HNSW crates assume the graph lives in a single allocation; we wanted a graph keyed into a RocksDB column family with a coarse per-index lock, so that `open()` restores from disk without rebuilding and a SIGKILL mid-insert recovers atomically with the row. Retrofitting that onto an upstream crate would have been worse than writing it. ## P2 — the HNSW graph itself Malkov & Yashunin's algorithm, level assignment via public-domain SplitMix64 (so reindexing is reproducible across machines without dragging in a CSPRNG dependency). The graph is a per-element neighbour list per level; we picked the layout that round-trips cleanly to RocksDB without a serialisation library — three column-family keys per element rather than a single blob, so partial updates during `remove()` don't rewrite the whole node. ## P1 — persistence and recovery The index lives in a single RocksDB instance under the `__vidx:` keyspace. `open()` walks the keyspace once on startup, restores the entry-point pointer, and is ready to answer queries — no graph rebuild, no codebook regeneration. Crash recovery is the standard RocksDB-WAL story: every `insert()` / `remove()` writes a batch; on restart, RocksDB replays the WAL and the index is whole. Coarse per-index locking — we explicitly did not chase fine-grained concurrency in P1; getting the persistence shape right was higher value than getting parallel writers to scale. ## P3 — online deletes with neighbour repair Tombstone-only deletes are the trap. They look fine in tests (recall stays high until you've deleted a few percent), and they look wrong in production six months later (recall drops, p99 climbs, you can't tell why). `remove()` in v3.32 walks the affected node's incoming-edge set and rewrites each neighbour's adjacency list to drop the deleted entry — the graph stays connected, the entry-point invariant holds, and recall doesn't rot. `compact()` reclaims the tombstoned RocksDB keyspace when the dead-node ratio gets high. Same shape as RocksDB's own compaction, one level up. ## P4 — Product Quantization with ADC traversal and two-stage rerank PQ basics: split a D-dim vector into M sub-vectors of D/M dims each, k-means each sub-space into 256 centroids, store each vector as M bytes (the centroid id per sub-space). Distance between a query and a code is summed from M pre-computed lookup tables — Asymmetric Distance Computation. ~16× compression vs raw F32. The trick that keeps recall: **two-stage exact rerank.** The graph traversal uses PQ codes (fast, approximate); for the candidate set returned at the top of the graph, we load the full vectors from disk and rerank against the query for exact ordering. The candidate set is a small multiple of k, so the rerank cost is negligible. PQ-vs-exact recall@10: 0.987 vs 0.989 on the canonical fixture. One catch we fixed in v3.32.1: `ProductQuantizerConfig::default_for_dimension` picked too few sub-quantizers for common embedding dimensions, collapsing recall on any caller using defaults — including the SQL `CREATE INDEX … USING hnsw` PQ path and `quantized_hnsw`. New default: ~4 dimensions per sub-vector. The default-path regression test we added with the fix would have caught it; every prior PQ test passed an explicit config, which is how it slipped through. Found by the [CodeKB MCP](https://www.heliosdb.com/codekb-mcp.html) team's adoption smoke. ## P5 — filtered KNN, evaluated during traversal Post-filter is wrong for vector search. If a top-50 has 47 rows that fail your `WHERE tenant_id = $1` filter, you get top-3 instead of top-k. The right shape is "top-k that pass the filter" — and the only way to get that is to evaluate the predicate inside the graph traversal, expanding the search until k passing neighbours are found. `search_filtered` takes a closure; the closure is called per candidate during traversal, not after. ## P6 — multi-precision rerank vectors The rerank vectors don't have to be F32. F16 (hand-rolled IEEE half — no `half` crate dependency) halves the rerank-store size; I8 scalar quantization quarters it. Pick the precision dial that matches your recall budget. Zero new dependencies — the conversion is a tight bit-twiddle loop. ## P7 — validation and head-to-head vs main Two reports shipped in-tree: - `VALIDATION_REPORT_persistent_pq_hnsw.md` — the feature's own recall / memory / latency characterisation, plus a persistence round-trip check (drop → reopen → identical top-10). - `BENCHMARK_main_vs_persistent_pq_hnsw.md` — the no-regression gate. `git worktree` checkout of `main` alongside the branch, `cargo bench` default features (so `vector-persist` is OFF and the new code isn't compiled), same machine, ~10 min apart. The `art_index_bench` + `vector_search_bench` deltas scatter bidirectionally (−13 % … +16 %) — machine noise, not code. The entire delta is gated behind `#[cfg(feature = "vector-persist")]`, so the default binary is byte-identical to v3.31.2. ## What's not there yet SQL `CREATE INDEX` wiring for the persistent path. Today the new `PersistentVectorIndex` is a Rust library API — the same way the engine drives `code_index` and `graph_rag_ingest_docs`. Wiring it into DDL is on the roadmap and will appear in a later 3.32.x or 3.33.x release. Also: PQ is L2-only. Embedding models that produce normalised vectors (BGE-Small, OpenAI `text-embedding-3-*`, most modern open models) work natively because cosine ≈ L2 on the unit sphere. Inner-product PQ is a separate problem we have not solved. HeliosDB Nano is Apache 2.0. Repository: [github.com/dimensigon/HDB-HeliosDB-Nano](https://github.com/dimensigon/HDB-HeliosDB-Nano). Branch: `feat/persistent-pq-hnsw` (merged), commits `87b0497` through `4048e93`.