# ruvector 2026: Batched HNSW with Shared Candidate Frontier — Rust vector search, 71-97% fewer vector loads on correlated query batches (RAG, ColBERT/MaxSim, MMR), zero recall loss.

> Source: <https://gist.github.com/CrossGen-ai/b5ca246073a1f8e109232ec501a86458>
> Published: 2026-09-26 17:06:20+00:00

**Summary (≤150 chars):** Rust HNSW backend that shares candidate vectors across correlated query batches — saves 71-97% vector loads, 1.24× faster, zero recall loss.

If your Rust vector search workload is a RAG loop with multi-turn queries, an MMR / diverse-beam reranker, or a multi-vector retrieval (ColBERT / MaxSim / MuVera), you are running **correlated query batches** — and every mainstream HNSW library (FAISS, Milvus, Qdrant, Weaviate, Pinecone, LanceDB) treats those queries as independent, re-loading each candidate vector's cache lines *Q* times. This ruvector nightly research (2026-09-26, ADR-347) publishes a Rust HNSW search backend that shares distance computations across the batch: **71 – 97 % fewer vector loads** and **1.24 × faster wall clock at Q = 16** on Apple M4 Max, with recall bit-for-bit identical to per-query search.

Keywords: rust vector search, HNSW, ANN, ruvector, batched search, RAG retrieval, ColBERT, multi-vector retrieval, approximate nearest neighbor, vector database.

- Three swappable backends behind one `BatchedSearch` trait:
  - `IndependentSearch` — baseline per-query greedy`ef` -search.
  - `BatchedKernelSearch` — one candidate vector × Q queries per distance call.
  - `SharedFrontierSearch` — batch-wide evaluated set + cached per-query distance rows.
- Deterministic (`rand_chacha` ), single-crate, no unsafe.
- Real bench binary (`cargo run --release --bin bsf-bench` ) that publishes verifiable numbers.
- 6 tests including a differential vector-load-count assertion.

- **Recall-preserving.** Each query still owns its own frontier heap and result heap; recall matches the independent baseline exactly.
- **Memory-bounded.** Cache footprint is`Q · N · 4` bytes worst case (~0.6 MiB at Q=32, N=5 000). Dense today, sparse-swappable for large N.
- **Drop-in.**`BatchedSearch` is a five-method trait; existing per-query call sites replace`search` with`search_batch` .

| System | Batch API | Distance sharing? | Recall preserved? | 
|---|---|---|---|
| **ruvector (this crate)** | `search_batch` | **Yes** (shared frontier + batched kernel) | **Yes** | 
| FAISS 1.8 | `search` (per-thread) | No | Yes | 
| Milvus 2.4 | `BatchSearch` | No | Yes | 
| Qdrant 1.10 | multi-vector query | No | Yes | 
| Weaviate | `nearVector[]` | No | Yes | 
| Pinecone | `query.top_k[]` | No | Yes | 
| LanceDB | `search().nearest()` | No | Yes | 

Apple M4 Max (arm64), Darwin 24.6.0, rustc 1.98.1, release profile.
Dataset: n = 5 000, dim = 128, 32 Gaussian clusters. Correlated batch generator.
`k = 10`, `ef = 64`. Numbers from `cargo run --release --bin bsf-bench`.

| Q | corr | independent (ms / loads) | shared-frontier (ms / loads / hits) | savings | recall | 
|---|---|---|---|---|---|
| 4 | 0.60 | 0.19 / 3 096 | 0.15 / 889 / 2 204 | **71.3 %** | 0.975 | 
| 4 | 0.98 | 0.17 / 3 101 | 0.14 / 808 / 2 290 | **73.9 %** | 1.000 | 
| 8 | 0.85 | 0.32 / 6 196 | 0.28 / 883 / 5 306 | **85.7 %** | 0.988 | 
| 8 | 0.98 | 0.31 / 6 204 | 0.24 / 824 / 5 373 | **86.7 %** | 1.000 | 
| 16 | 0.60 | 0.69 / 12 432 | 0.59 / 907 / 11 510 | **92.7 %** | 0.988 | 
| 16 | 0.98 | 0.61 / 12 436 | 0.49 / 828 / 11 593 | **93.3 %** | 1.000 | 
| 32 | 0.60 | 1.47 / 24 801 | 1.25 / 907 / 23 863 | **96.3 %** | 0.984 | 
| 32 | 0.98 | 1.12 / 24 828 | 1.00 / 835 / 23 962 | **96.6 %** | 1.000 | 

- **Vector-load savings 71 – 97 %** across the whole sweep.
- **Wall-clock speedup 1.10 – 1.24 ×** vs the independent baseline.
- **Zero recall degradation** — every backend returns identical top-k.

- **Batched L2 kernel** with a 4× query-row unroll keeps the candidate vector hot in registers across queries.
- **Dense `Q · N` distance-row cache** — branch-free hot path.
- **Per-query heaps** preserved so top-k semantics don't change.
- **Round-robin frontier scheduling** so cache-warmth is exploited.
- Future work (from the research doc): NEON / AVX-512 kernel, query-centroid warm-up, RaBitQ integration, sparse cache for N > 1 M, adaptive backend router.

- **Source (CrossGen-ai fork, research branch):**`https://github.com/CrossGen-ai/RuVector/tree/research/nightly/2026-09-26-hnsw-batch-shared-frontier/crates/ruvector-hnsw-batch-shared-frontier`
- **ADR:**`docs/adr/ADR-347-hnsw-batch-shared-frontier.md`
- **Research doc:**`docs/research/nightly/2026-09-26-hnsw-batch-shared-frontier/README.md`
- **Upstream project:**[github.com/ruvnet/RuVector](https://github.com/ruvnet/RuVector)

```
git clone https://github.com/CrossGen-ai/RuVector.git
cd RuVector
git checkout research/nightly/2026-09-26-hnsw-batch-shared-frontier
cargo test  --release -p ruvector-hnsw-batch-shared-frontier
cargo run   --release -p ruvector-hnsw-batch-shared-frontier --bin bsf-bench
```

Tags: `rust`, `hnsw`, `vector-search`, `ann`, `rag`, `ruvector`, `colbert`, `multi-vector-retrieval`, `nearest-neighbor`, `approximate-nearest-neighbor`.