# Performance Characteristics of VelesDB's HNSW Index: Speed, Recall, and Memory Trade-offs

> Explore VelesDB's HNSW index performance. Achieve up to 99% recall at 500 µs or 92% at 150 µs. Learn about speed, recall, and memory trade-offs.

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

---

**VelesDB's HNSW index delivers amortized O(log N) insertion and search complexity with configurable quality profiles that balance latency against recall, achieving up to 99% recall at ~500 µs latency or 92% recall at ~150 µs depending on the `ef_search` parameter.**

The `cyberlife-coder/velesdb` repository implements a native Hierarchical Navigable Small World (HNSW) index in Rust that prioritizes production-grade vector search performance. Understanding the performance characteristics of VelesDB's HNSW index requires examining its insertion throughput, search latency, memory footprint, and the tunable parameters that govern the speed-recall trade-off.

## Insertion Performance and Throughput

### Amortized O(log N) Graph Updates

In [`src/index/hnsw/index/mod.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/mod.rs), the core `HnswIndex` struct implements insertion with **amortized O(log N)** graph updates per vector. This logarithmic complexity emerges from the navigable small-world graph structure that maintains short-range and long-range links during construction.

Sequential insertion of 1,000 768-dimensional vectors completes in approximately **0.2 seconds** according to the benchmark suite in [`benches/hnsw_benchmark.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/benches/hnsw_benchmark.rs). This baseline performance assumes standard mode with full vector storage enabled for re-ranking capabilities.

### Fast-Insert Mode for Bulk Loading

For bulk ingestion scenarios, [`src/index/hnsw/index/constructors.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/constructors.rs) exposes the `new_fast_insert` constructor that creates an index skipping raw vector storage. This mode stores only the graph structure, yielding approximately **2× higher throughput** and **50% lower memory** consumption.

Benchmarks demonstrate that inserting 1,000 vectors in fast-insert mode requires only **≈0.09 seconds** compared to 0.18 seconds in standard mode. However, this optimization disables SIMD re-ranking and brute-force fallback mechanisms, making it suitable only for initial bulk loads followed by a transition to standard searching mode.

### Parallel Insertion with Rayon

The `insert_batch_parallel` function in [`src/index/hnsw/index/batch.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/batch.rs) leverages Rust's parallelism primitives to distribute insertion work across CPU cores. Parallel insertion of 10,000 vectors achieves approximately **2× speedup** over sequential insertion, scaling linearly with available CPU cores up to the graph's concurrency limits.

After bulk insertion completes, calling `set_searching_mode` from [`src/index/hnsw/index/search.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/search.rs) finalizes the graph structure and switches the index from construction to query-optimized state.

## Search Latency and Throughput Characteristics

### O(log N) Search Complexity

Search operations in VelesDB's HNSW index exhibit **O(log N)** complexity relative to index size. The implementation uses a multi-layer graph where the upper layers provide coarse navigation and lower layers refine nearest neighbor candidates.

For a 10,000-vector index with 768-dimensional cosine similarity queries, top-10 search latency ranges from **≈150 µs** in fast profile configuration to **≈500 µs** in balanced profile configuration. These measurements derive from the [`hnsw_benchmark.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/hnsw_benchmark.rs) latency benchmarks executed on standard hardware.

### Quality Profiles: Trading Speed for Recall

The [`src/index/hnsw/index/mod.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/mod.rs) file defines four quality profiles that map `ef_search` parameters to recall targets:

- **Fast** (`ef_search = 64`): Achieves approximately **92% recall** with the lowest latency (~150 µs), suitable for high-throughput filtering scenarios.
- **Balanced** (`ef_search = 128`): Default profile delivering approximately **99% recall** at moderate latency (~500 µs), recommended for production deployments.
- **Accurate** (`ef_search = 256`): Targets approximately **100% recall** with higher latency overhead, suitable for precision-critical applications.
- **Perfect** (`ef_search = 2048`): Maximum recall configuration with significant latency penalties, used for ground-truth validation or small datasets.

Search throughput scales inversely with `ef_search` values. The benchmark suite reports approximately **600 QPS** (queries per second) for top-10 searches on a 10,000-vector index using the balanced profile.

## Memory Footprint and Storage Modes

Memory consumption in VelesDB's HNSW index depends on graph structure storage and optional raw vector retention. For a 10,000-vector index with 768-dimensional vectors:

- **Standard mode**: Approximately **250 MiB** total memory, including full vector storage for re-ranking and brute-force fallbacks.
- **Fast-insert mode**: Approximately **120 MiB** total memory, storing only the graph structure without raw vectors.

The [`src/index/hnsw/persistence.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/persistence.rs) module handles on-disk serialization of graph and metadata, enabling memory-mapped loading for large indices that exceed RAM capacity.

## Benchmarking Methodology

Performance metrics derive from the comprehensive benchmark suite in [`crates/velesdb-core/benches/hnsw_benchmark.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/crates/velesdb-core/benches/hnsw_benchmark.rs). This suite measures:

1. **Sequential insertion** latency for varying vector counts (1,000 to 100,000)
2. **Parallel insertion** throughput across CPU core counts
3. **Fast-insert mode** performance without vector storage
4. **Search latency** percentiles (p50, p95, p99) for top-k queries
5. **Throughput** in queries per second (QPS)
6. **Recall validation** against brute-force ground truth for dimensions 128 through 3072

Recall validation asserts **≥95% average recall** for dimensions up to 3072 using the balanced profile, confirming production-grade accuracy across diverse vector sizes.

## Code Examples: Configuring HNSW Performance

The following examples demonstrate how to instantiate and configure VelesDB's HNSW index for different performance profiles:

```rust
use velesdb_core::{Collection, DistanceMetric, HnswIndex, Point, VectorIndex};

/// Create a standard HNSW index (balanced profile)
let mut index = HnswIndex::new(768, DistanceMetric::Cosine);

/// Insert vectors (sequential)
for id in 0..10_000u64 {
    let vec = (0..768).map(|i| ((id as f32) * 0.01 + i as f32 * 0.001).sin()).collect::<Vec<_>>();
    index.insert(id, &vec);
}
index.set_searching_mode(); // switch to query mode

/// Fast‑insert mode (no raw vector storage)
let mut fast = HnswIndex::new_fast_insert(768, DistanceMetric::Cosine);
fast.insert_batch_parallel(/* pre‑generated vectors */);
fast.set_searching_mode();

/// Perform a top‑10 search
let query = vec![0.5f32; 768];
let results = index.search(&query, 10);
println!("Top‑10 IDs: {:?}", results.iter().map(|(id, _)| id).collect::<Vec<_>>());

/// Use the index inside a collection (persistence)
let collection = Collection::create("my_collection", 768, DistanceMetric::Cosine).unwrap();
collection.upsert(vec![Point::without_payload(1, query.clone())]).unwrap();
let hits = collection.search(&query, 10);
println!("Collection search results: {:?}", hits);

```

Key implementation files referenced:
- [`src/index/hnsw/index/constructors.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/constructors.rs) – Contains `new`, `new_fast_insert`, and `new_turbo` constructors
- [`src/index/hnsw/index/batch.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/batch.rs) – Implements `insert_batch_parallel` for multi-threaded ingestion
- [`src/index/hnsw/index/search.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/search.rs) – Defines `set_searching_mode` and search execution logic

## Summary

- **Insertion complexity** is amortized O(log N) per vector, with sequential insertion of 1,000 768-dimensional vectors completing in ~0.2 seconds and parallel insertion achieving 2× speedup via `insert_batch_parallel`.
- **Fast-insert mode** trades functionality for speed, storing only graph structures to achieve ~0.09 seconds per 1,000 vectors and 50% memory reduction, but disables re-ranking and brute-force fallbacks.
- **Search latency** ranges from ~150 µs (fast profile) to ~500 µs (balanced profile) for top-10 queries on 10,000 vectors, with complexity O(log N) relative to index size.
- **Recall rates** are tunable via quality profiles: 92% recall (`ef_search=64`), 99% recall (`ef_search=128`, default), or 100% recall (`ef_search=256+`).
- **Memory footprint** varies by storage mode: ~250 MiB for standard mode with full vector storage versus ~120 MiB for fast-insert mode on a 10,000-vector 768-dimensional index.

## Frequently Asked Questions

### What is the time complexity of VelesDB's HNSW index operations?

VelesDB's HNSW index implements **amortized O(log N)** complexity for both insertion and search operations. This logarithmic scaling emerges from the hierarchical navigable small-world graph structure maintained in [`src/index/hnsw/index/mod.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/mod.rs), where upper layers provide coarse navigation and lower layers refine nearest neighbor candidates. For a 10,000-vector index, this translates to microsecond-scale search latencies rather than the linear scan time required by brute-force approaches.

### How does the fast-insert mode affect search quality and recall?

Fast-insert mode significantly impacts search capabilities by disabling **raw vector storage** and **SIMD re-ranking**. When instantiated via `HnswIndex::new_fast_insert` in [`src/index/hnsw/index/constructors.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/constructors.rs), the index stores only graph connectivity without the original 768-dimensional vectors, reducing memory by approximately 50%. However, this eliminates the brute-force fallback and re-ranking stage that typically improves recall precision. Consequently, fast-insert mode is recommended exclusively for initial bulk data ingestion followed by a transition to standard searching mode via `set_searching_mode`.

### What are the recommended quality profiles for production workloads?

For production deployments, the **Balanced** quality profile (`ef_search = 128`) provides the optimal trade-off between latency and accuracy, achieving approximately **99% recall** with search latencies around 500 µs for 10,000-vector datasets. This profile is defined in [`src/index/hnsw/index/mod.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/mod.rs) and serves as the default configuration. For high-throughput filtering scenarios where approximate results suffice, the **Fast** profile (`ef_search = 64`) delivers 92% recall at ~150 µs latency. For precision-critical applications such as ground-truth validation, the **Accurate** (`ef_search = 256`) or **Perfect** (`ef_search = 2048`) profiles provide near-100% recall at the cost of increased query latency.

### How does parallel insertion scale with CPU cores?

Parallel insertion scales **linearly with CPU cores** up to the graph's concurrency limits through the `insert_batch_parallel` function implemented in [`src/index/hnsw/index/batch.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/batch.rs). Benchmarks in [`benches/hnsw_benchmark.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/benches/hnsw_benchmark.rs) demonstrate that inserting 10,000 vectors in parallel achieves approximately **2× speedup** compared to sequential insertion, distributing work via Rust's parallelism primitives similar to `rayon`. This makes parallel insertion highly effective for large bulk loads, though developers must call `set_searching_mode` from [`src/index/hnsw/index/search.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/src/index/hnsw/index/search.rs) after completion to finalize the graph structure for query operations.