How VelesDB Implements Approximate Nearest Neighbor Search with HNSW

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.

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) 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:

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 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) 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 (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 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:

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:

• 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. 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, 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}