Index Types Explained: HNSW, IVF, and Flat – Performance Characteristics

Vector database architectures for retrieval-augmented generation (RAG) rely heavily on efficient indexing to balance recall quality and query speed. The principal index types in use today include Hierarchical Navigable Small World graphs (HNSW), Inverted File (IVF) indexing, and brute-force Flat scans. Each has distinct trade-offs relevant to enterprise implementations.

Flat Index: Baseline Accuracy and Latency

The Flat index performs exhaustive nearest neighbor search by computing distance metrics between the query vector and every vector in the database. It guarantees exact recall but scales linearly with dataset size. Benchmarks from Milvus v2.2 demonstrate query latency exceeding 100 milliseconds for datasets in the 10 million vector range on commodity hardware.

Flat indexes are most suitable for datasets under one million vectors or scenarios where recall precision must be 100% under all conditions. The computational cost and memory footprint, however, grow directly with database size and dimensionality.

Inverted File (IVF): Balancing Speed and Recall

IVF indexes partition the vector space into clusters, reducing search scope to a subset of relevant partitions. The IVF approach is often combined with Product Quantization (PQ) for compressed storage and faster distance approximations. According to FAISS benchmarks, IVF indexes can reduce query latency by an order of magnitude compared to Flat scans at recall rates around 90%.

IVF's performance depends heavily on parameters like the number of clusters and probes per query. Increasing probes improves recall but increases latency. In production systems such as Pinecone and Weaviate, IVF is favored for datasets ranging from one million to hundreds of millions of vectors, delivering sub-50 millisecond latencies with recall typically above 85%.

IVF requires pre-processing overhead for clustering and periodic re-training as new data comes in. It also places moderate demands on memory to store cluster centroids.

Hierarchical Navigable Small World (HNSW): Low Latency and High Recall

HNSW leverages a multi-layer graph structure to perform approximate nearest neighbor search by navigating links between nodes. This approach balances low latency and high recall, often achieving 95%–99% recall with query latencies under 10 milliseconds on vectors numbering in the tens of millions.

The efficiency of HNSW comes from logarithmic search complexity relative to dataset size, demonstrated in benchmarks such as those from NMSLIB and Elasticsearch k-NN plugin. Memory use is higher because the graph maintains multiple edges per vector, but this trade-off enables rapid queries without sacrificing much recall.

HNSW's incremental insertion and deletion capabilities make it suitable for dynamic datasets, a key advantage over IVF which often requires cluster re-computation upon bulk changes.

Comparative Summary and Use-Case Guidance

In selecting an index type, engineering teams must weigh latency, recall, dataset size, and update frequency. Flat indexes excel in accuracy but suffer in query speed and resource cost for large datasets. IVF offers configurable balance but requires cluster tuning and batch re-indexing. HNSW delivers low-latency high recall and supports dynamic data, though with increased memory overhead.

For RAG applications serving tens to hundreds of millions of vectors with strict latency SLAs under 20 milliseconds, HNSW currently represents the best compromise. IVF remains viable when memory is constrained and latency can be tolerated up to 50 milliseconds. Flat indexes function as a fallback for very small or specialized use cases demanding exact search.