# How VelesDB Implements Approximate Nearest Neighbor Search with HNSW

> Discover how VelesDB implements approximate nearest neighbor search with HNSW using its native Rust engine. Explore SIMD acceleration, hierarchical traversal, and adaptive multi-probe strategies for efficient search.

- Repository: [Wiscale/velesdb](https://github.com/cyberlife-coder/velesdb)
- Tags: deep-dive
- Published: 2026-02-28

---

**VelesDB implements approximate nearest neighbor search with HNSW through a native Rust engine in `velesdb-core` that replaces the external `hnsw_rs` crate, featuring SIMD-accelerated distance computation, hierarchical graph traversal, and adaptive multi-probe search strategies.**

VelesDB ships a production-ready native HNSW (Hierarchical Navigable Small World) implementation that delivers sub-millisecond query latency for high-dimensional vector search. Located in the `velesdb-core` crate under `src/index/hnsw/native/`, this engine provides the `NativeHnswIndex` API as a drop-in replacement for external HNSW libraries. The implementation combines SIMD-vectorized distance engines with sophisticated graph traversal algorithms to optimize the recall-latency trade-off inherent in approximate nearest neighbor search with HNSW.

## Core Architecture and Graph Structure

The native HNSW engine organizes vectors into a hierarchical graph structure defined in [`src/index/hnsw/native/mod.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native/mod.rs).

### Layered Graph Organization

At the center of the implementation is `NativeHnsw<D>`, a generic structure parameterized by a distance engine `D`. The graph consists of multiple **layers** containing **nodes** (`Layer` and `NodeId` types), where each node maintains connections to neighbors within its layer. The bottom layer contains the full dataset, while upper layers serve as "expressways" for fast traversal, following the original HNSW paper by Malkov and Yashunin (2016) as referenced in the source documentation.

### SIMD-Accelerated Distance Engines

Distance computation is optimized through pluggable engines selectable at index creation time:

- **`CachedSimdDistance`** — SIMD-vectorized engine with caching for repeated calculations
- **`CpuDistance`** — Standard CPU-based fallback
- **`NativeSimdDistance`** — Native SIMD intrinsics implementation

These engines support **Euclidean**, **Cosine**, **Dot-Product**, **Hamming**, **Jaccard**, and quantized distance metrics. The engine selection directly impacts search throughput, with `CachedSimdDistance` typically providing the best performance for high-dimensional data.

## Index Construction and Vector Insertion

Building the index involves layer-by-layer graph construction controlled by the `HnswParams` configuration struct.

### Graph Building Process

The `NativeHnswInner::insert` method (located in [`src/index/hnsw/native_inner.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native_inner.rs)) handles single-vector insertion by auto-assigning a `NodeId` and establishing connections according to the `max_connections` parameter. For bulk loading scenarios, the engine provides **`parallel_insert`**, which optimizes throughput by constructing the graph concurrently.

The **`ef_construction`** parameter controls the quality of the graph during build time—higher values create denser connections and improve search recall at the cost of slower insertion. The implementation automatically manages neighbor selection and bidirectional connection updates as specified in the original HNSW algorithm.

### Parameter Tuning Strategies

VelesDB exposes three parameter presets via [`src/index/hnsw/params.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/params.rs):

1. **`HnswParams::auto`** — Derives sensible defaults based on vector dimensionality
2. **`HnswParams::turbo`** — Maximizes insert throughput for initial data loading
3. **Custom parameters** — Set via `NativeHnswIndex::with_params` for fine-grained control of `max_connections`, `ef_construction`, and layer distribution

## Search Algorithms and Optimization

The search implementation in [`src/index/hnsw/native/graph/search.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native/graph/search.rs) combines standard HNSW traversal with VelesDB-specific optimizations.

### Hierarchical Greedy Descent

The search process begins at the top layer and performs a **greedy descent** using `search_layer_single`. This function walks each upper layer to find the closest entry point for the next layer down, rapidly approaching the query vector's local neighborhood without examining the full dataset.

### Bottom-Layer EF Search

Once reaching layer 0 (the bottom layer), `search_layer` executes the main **ef-search** algorithm:

- Maintains a binary heap of candidates ordered by distance
- Tracks visited nodes to prevent cycles
- Expands neighbors up to the `ef_search` limit
- Implements **early exit** when the farthest candidate in the result set is closer than any unseen node
- Uses **prefetching** for dimensions > 384 to hide memory latency during neighbor expansion

The `ef_search` parameter directly controls the recall-latency trade-off, with typical values ranging from 50 (fast) to 200 (high recall).

### Adaptive Multi-Probe Strategy

For hard queries or high `ef_search` values, **`search_multi_entry`** (lines 53-71 in [`search.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/search.rs)) implements an **adaptive multi-probe** strategy:

- Generates up to four random entry points using an **XorShift RNG**
- Executes parallel searches from each entry point
- Merges candidate sets to improve recall without increasing per-probe latency

The `adaptive_num_probes` parameter automatically determines when to activate multi-probe mode based on query difficulty indicators.

## Concurrency and Persistence

The native HNSW engine provides thread-safe access and durable storage mechanisms.

### Thread Safety

As implemented in [`src/index/hnsw/native_inner.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native_inner.rs) (lines 41-50), the graph structure and vector storage are wrapped in **`RwLock`** primitives. The `NativeHnswInner` type implements both **`Send`** and **`Sync`**, allowing concurrent reads and exclusive writes across threads without compromising graph integrity.

### Binary Serialization

Persistence is handled through `NativeHnswInner::file_dump` and `file_load`, which serialize the graph to a binary format (`native_hnsw`) alongside metadata (`HnswMeta`). The high-level `NativeHnswIndex` type in [`src/index/hnsw/native_index.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native_index.rs) coordinates saving and loading of the graph structure, ID mappings, and optional vector storage, enabling complete index recovery between process restarts.

## Practical Implementation Example

The following example demonstrates creating, populating, and querying a native HNSW index:

```rust
use velesdb_core::{
    index::hnsw::native::NativeHnswIndex,
    distance::DistanceMetric,
};

fn main() -> std::io::Result<()> {
    // Create a 128-dimensional index using Euclidean distance
    let mut index = NativeHnswIndex::new(128, DistanceMetric::L2);

    // Insert 10,000 random vectors with external IDs
    for i in 0..10_000 {
        let vec: Vec<f32> = (0..128).map(|_| rand::random::<f32>()).collect();
        index.insert(vec, i);
    }

    // Persist the index to disk
    index.save("my_hnsw_index")?;

    // Search for 5 nearest neighbors
    let query: Vec<f32> = (0..128).map(|_| rand::random::<f32>()).collect();
    let results = index.search(&query, 5, 100);

    for (id, distance) in results {
        println!("id = {}, distance = {:.4}", id, distance);
    }

    Ok(())
}

```

Key API methods from [`src/index/hnsw/native_index.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native_index.rs):
- **`NativeHnswIndex::new`** (lines 48-55) — Constructs an index with auto-tuned parameters
- **`index.insert`** (lines 83-95) — Inserts vectors and registers external IDs in `ShardedMappings`
- **`index.search`** (lines 158-170) — Executes ANN search returning `Vec<(usize, f32)>`
- **`index.save`** (lines 91-121) — Serializes the complete index state

## Summary

- VelesDB implements approximate nearest neighbor search with HNSW through a native Rust engine in `velesdb-core`, eliminating dependencies on external crates like `hnsw_rs`.
- The architecture uses **SIMD-accelerated distance engines** (`CachedSimdDistance`, `CpuDistance`) to compute Euclidean, Cosine, and other metrics with hardware optimization.
- **Graph construction** occurs via `NativeHnswInner::insert` and `parallel_insert`, controlled by `max_connections` and `ef_construction` parameters from `HnswParams`.
- **Search** combines hierarchical greedy descent (`search_layer_single`) with bottom-layer ef-search (`search_layer`) and optional **multi-probe** entry points (`search_multi_entry`) for high-recall scenarios.
- The implementation is **thread-safe** (`Send`/`Sync` with `RwLock` wrapping) and supports **binary persistence** through `file_dump` and `file_load` operations.
- **Prefetching** optimizations activate automatically for high-dimensional vectors (>384 dimensions) to mask memory latency.

## Frequently Asked Questions

### How does VelesDB's native HNSW implementation differ from standard HNSW libraries?

VelesDB replaces external dependencies like `hnsw_rs` with a custom implementation optimized for the database's specific latency and concurrency requirements. Unlike generic libraries, VelesDB's native version integrates **adaptive multi-probe search** (`adaptive_num_probes`), automatic prefetching for high-dimensional data, and SIMD-engine selection at the index level. The implementation also provides seamless persistence through `NativeHnswIndex::save` and coordinated loading of graph metadata alongside vector mappings.

### What role does SIMD play in the distance computation?

SIMD (Single Instruction, Multiple Data) acceleration is provided by the `CachedSimdDistance` and `NativeSimdDistance` engines in [`src/index/hnsw/native/distance.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native/distance.rs). These engines use CPU vector instructions to compute distances between high-dimensional vectors in parallel chunks, significantly reducing the arithmetic cost of the inner loop during both graph construction and search. The **cached** variant additionally memoizes intermediate results to avoid redundant calculations during repeated distance computations in dense graph neighborhoods.

### How should I tune `ef_construction` and `ef_search` for my workload?

Set **`ef_construction`** high (200-400) during initial index building if you prioritize search recall over ingestion speed, or use `HnswParams::turbo` for bulk loading. For **`ef_search`**, start with values equal to your target **k** (number of neighbors) for latency-sensitive queries, or use 50-100 for balanced performance. The `search_multi_entry` function automatically engages when `ef_search` exceeds certain thresholds, distributing the recall cost across multiple random entry points rather than increasing single-search complexity.

### Is the native HNSW implementation thread-safe for concurrent reads and writes?

Yes. According to the implementation in [`src/index/hnsw/native_inner.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/native_inner.rs), the graph and underlying vectors are protected by **`RwLock`** primitives, and the `NativeHnswInner` type explicitly implements **`Send`** and **`Sync`**. This allows multiple threads to execute concurrent searches (read locks) while safely excluding writers during insertion operations. For maximum read throughput, searches can execute fully in parallel across threads without blocking each other.