Why We Chose HNSW Over Other Vector Indexes

Why We Chose HNSW Over Other Vector Indexes

When we started building Uteke's vector search layer, the first decision was which index algorithm to use. We evaluated several options before settling on HNSW. Here is the decision process and the tradeoffs we considered.

The Contenders

• Flat (brute force)
• — Compare every vector against the query. Simple, perfect recall, but O(n) latency. Doesn't scale past a few thousand entries.
• IVF (Inverted File)
• — Partition vectors into clusters, search only nearby clusters. Faster than flat, but recall drops with fewer clusters probed.
• Annoy (Spotify)
• — Tree-based approach with random projections. Fast build, decent query speed, but higher memory usage and harder to tune.
• HNSW
• — Layered graph structure. Fast queries with high recall. Best tradeoff for our use case.

Our Requirements

Uteke targets datasets from 1K to 100K memories, running on CPU, with sub-10ms recall latency. The index must support incremental inserts (memories are added one at a time as agents run), and memory usage should stay reasonable without a GPU.

Why HNSW Won

Query speed: HNSW's layered graph gives logarithmic query time. At 10K entries, most queries visit fewer than 50 nodes. Compare this to brute force which visits all 10K.

Recall quality: HNSW consistently achieves 95%+ recall@10 with default parameters. IVF requires careful tuning to reach similar recall.

Incremental inserts: Adding a new memory to HNSW is a single insert operation — no retraining or reindexing. IVF and flat don't have this issue either, but tree-based methods often need rebalancing.

Memory efficiency: At 384 dimensions and 10K entries, HNSW uses roughly 15MB. Annoy's random projections double the memory footprint for similar recall.

The Tradeoffs

HNSW is not perfect. Build time is slower than flat or IVF (though for incremental inserts this doesn't matter). Memory usage grows faster than IVF at very large scales (millions of entries). And parameter tuning (efConstruction, M, efSearch) requires some experimentation.

For our target scale (up to 100K entries on CPU), these tradeoffs are acceptable. HNSW gives us the best query latency while maintaining high recall, which is what matters for real-time agent memory.

Implementation

We use the hnsw crate in Rust, which provides a native HNSW implementation with good ergonomics. The index is serialized alongside the SQLite database and loaded into memory on startup.

The original HNSW paper by Malkov and Yashunin is available on arXiv.