Tag: algorithms

Every retrieval-augmented generation (RAG) pipeline, semantic search box, and recommendation engine built since 2023 depends on the same underlying problem: given a query vector, find the handful of vectors in a database of millions (or billions) that are closest to it. Doing this exactly, by comparing the query to every stored vector, is called k-nearest neighbor (kNN) search, and it does not scale — brute-force comparison is O(N) per query. So almost every real vector database instead does approximate nearest neighbor (ANN) search: trading a small, tunable amount of recall for orders-of-magnitude faster lookups. Two families of ANN algorithm dominate production systems in 2026: graph-based methods, led by HNSW, and partition-based methods, led by IVF. This piece explains how each actually works, what their real trade-offs are, and when to reach for which.

At a Glance

Why Exact Search Doesn’t Scale

An embedding model turns text, images, or audio into a dense vector, typically a few hundred to a few thousand floating-point numbers, positioned so that semantically similar inputs land close together under a distance metric like cosine similarity or Euclidean distance. Finding the true nearest neighbors to a query vector means computing that distance against every vector in the collection. At a few thousand vectors this is trivial. At tens of millions, it means billions of floating-point operations per query — workable for a batch job, unworkable for an interactive RAG endpoint that needs to return results in tens of milliseconds. ANN algorithms accept a small, measurable chance of missing a true nearest neighbor in exchange for search that scales sub-linearly.

How HNSW Works

HNSW (Hierarchical Navigable Small World) was introduced by Yu. A. Malkov and D. A. Yashunin in their 2016 paper “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs,” building on earlier skip-list and small-world-graph ideas. Conceptually, HNSW organizes vectors into several stacked graph layers, like a multi-level transit map:

• The top layer is sparse, with a small number of nodes connected over long links — good for covering large distances quickly.
• Each layer below is progressively denser, with more nodes and shorter, more local connections.
• The bottom layer contains every vector in the collection, densely interconnected.

A search starts at an entry point in the top layer and greedily walks toward the query vector, hopping to whichever neighbor is closer at each step. When no neighbor in the current layer is closer, the search drops down a layer and continues, refining its position until it bottoms out with a set of nearby candidates. This is similar to zooming from a country-level map down to a street-level map rather than scanning every street in the country directly.

Three parameters control the trade-off, as documented by vector database vendors such as Qdrant:

• M — the maximum number of connections per node (commonly 8–64; Qdrant defaults to 16). Higher M improves recall but increases memory and build time.
• efConstruction — how many candidate neighbors are evaluated when inserting a new vector into the graph (commonly 100–500). Higher values build a better-connected graph at the cost of slower indexing.
• efSearch (sometimes called hnsw_ef) — how many candidates are evaluated per query at search time (commonly 50–200+). This is the main dial for trading query latency against recall, and unlike the other two, it can be changed per query without rebuilding the index.

HNSW’s practical downside is memory and mutability. The graph’s edges sit on top of the raw (or quantized) vectors, adding roughly M × 2 × 4 bytes per vector according to FAISS’s own documentation, and removing a vector cleanly is not supported because deleting a node can disconnect the graph around it — most implementations instead mark vectors as deleted and periodically rebuild.

How IVF Works

IVF (Inverted File index), as implemented in Meta’s FAISS library, takes a completely different approach: partition first, then search only the relevant partitions. FAISS’s own wiki documentation describes it as a “cell-probe method”:

• During index training, a coarse quantizer (usually k-means) splits the vector space into nlist cells, each represented by a centroid.
• Every vector in the collection is assigned to exactly one cell — whichever centroid it’s closest to — and stored in that cell’s inverted list.
• At query time, the query vector is compared only against the nlist centroids to find the nprobe closest cells, then compared against the actual vectors inside just those cells.

FAISS’s documentation gives a rule of thumb for sizing nlist at roughly C × sqrt(n) for a dataset of n vectors. The fraction of the database actually scanned per query is approximately nprobe / nlist (in practice usually a bit more, since cells are rarely perfectly balanced). Raising nprobe improves recall by checking more cells, at a roughly linear cost in query time. Recall suffers specifically when a query’s true nearest neighbor happens to sit in a cell that wasn’t among the nprobe probed — a structural risk near cell boundaries that has no direct HNSW equivalent.

IVF is commonly paired with vector compression. IVFFlat stores full-precision vectors (about 4d + 8 bytes per vector, where d is dimensionality); IVFPQ (product quantization) compresses vectors much further at some recall cost, making it attractive for billion-scale, memory-constrained deployments. Because cells are just lists, adding and removing vectors is straightforward compared to HNSW’s graph surgery problem.

A Minimal Illustration of the Search Logic

The pseudocode below is a simplified sketch of the two query paths — not production code — meant only to show where each algorithm spends its effort.

function ivf_search(query, nprobe):
    centroids = get_cell_centroids()
    nearest_cells = top_k(centroids, query, k=nprobe)
    candidates = []
    for cell in nearest_cells:
        candidates.extend(cell.vectors)
    return top_k(candidates, query, k=final_k)

function hnsw_search(query, ef_search):
    layer = top_layer
    current = entry_point
    while layer > 0:
        current = greedy_walk(layer, current, query)
        layer = layer - 1
    candidates = explore_neighbors(current, query, ef=ef_search)
    return top_k(candidates, query, k=final_k)

HNSW vs IVF: When to Use Which

Neither structure is strictly better; they sit at different points on the recall/speed/memory curve, and the right choice depends on dataset size, update frequency, and hardware budget.

• Choose HNSW when query latency matters most, the dataset fits comfortably in memory, recall needs to stay high even at low latency, and updates are frequent but deletions are rare (most RAG and real-time semantic search use cases). It’s the default or primary index type in Qdrant, Weaviate, and pgvector’s HNSW mode.
• Choose IVF (often IVF+PQ) when the collection is very large (hundreds of millions to billions of vectors), memory is tight, and some recall can be traded for dramatically smaller index size. It’s also easier to shard and rebuild incrementally, which is why it shows up heavily in FAISS-based offline and batch retrieval pipelines.
• Hybrid approaches exist: FAISS supports using an HNSW graph as the coarse quantizer inside an IVF index (IVF_HNSW), combining fast coarse routing with inverted-list storage.

In practice, most teams don’t hand-pick an algorithm from first principles — they pick a vector database (Qdrant, Weaviate, Pinecone, Milvus, or Postgres with pgvector) and then tune its exposed parameters. Pinecone’s newer serverless indexes go a step further and abstract the index type away entirely, separating storage from query compute and exposing on-demand read capacity rather than a pod size the user has to choose. That’s a trend worth watching: the HNSW-vs-IVF decision is increasingly made by the database vendor, not the application developer, with the practitioner left tuning recall targets and cost rather than graph parameters directly.

Trade-offs Summary

• Pros of HNSW: excellent recall-to-latency ratio, logarithmic-ish query scaling, tunable at query time via efSearch without rebuilding.
• Cons of HNSW: larger memory footprint, slower builds at high quality settings, poor support for deletions.
• Pros of IVF: lower memory overhead (especially with PQ), faster builds, straightforward updates and deletions, scales well to very large, sharded datasets.
• Cons of IVF: recall is more sensitive to data distribution and cell boundaries; needs careful nlist/nprobe tuning and periodic retraining of centroids as data shifts.

The Bottom Line

HNSW and IVF solve the same problem — fast approximate retrieval over dense vectors — with opposite structural bets: a navigable graph versus a partitioned index. For most RAG and application-facing semantic search workloads where the data fits in memory and queries need to be fast and fresh, HNSW’s recall-per-millisecond is hard to beat, which is why it has become the default in most purpose-built vector databases. For very large-scale, storage-constrained, or heavily batch-oriented retrieval, IVF (particularly IVF+PQ) remains the more economical choice. The practical skill isn’t memorizing one algorithm — it’s knowing which knobs (efSearch, nprobe, M, nlist) to turn when recall, latency, or memory becomes the bottleneck in production.

FAQ

Is ANN search ever exact?
No — by definition, approximate nearest neighbor search can miss some true nearest neighbors. Both HNSW and IVF expose parameters (efSearch, nprobe) that push recall closer to exact search as you increase them, at the cost of query speed.

Can I combine HNSW and IVF?
Yes. FAISS supports using an HNSW graph as the coarse quantizer inside an IVF index, and several systems layer quantization (scalar or product quantization) on top of either structure to shrink memory further.

Which one do most vector databases use by default?
Most purpose-built vector databases aimed at application developers — Qdrant, Weaviate, Milvus’s default configuration, pgvector’s HNSW index type — default to HNSW because of its strong recall-to-latency ratio on in-memory datasets. IVF (and IVF+PQ specifically) is more common in large-scale, cost-sensitive, or research/offline retrieval pipelines built directly on FAISS.

Does deleting vectors work the same way in both?
No. FAISS’s own documentation notes that HNSW does not support true vector removal because deleting a node can disconnect the graph; most systems instead tombstone and periodically rebuild. IVF’s list-based structure makes removal and insertion more straightforward.

How does this relate to RAG?
A RAG pipeline embeds a user’s query, runs ANN search (HNSW or IVF, depending on the vector store) against a corpus of pre-embedded chunks, and feeds the top results into an LLM’s context window as retrieved evidence. The ANN index’s recall directly caps how good the retrieved context — and therefore the generated answer — can be.

Sources

• Malkov & Yashunin, “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs” (arXiv:1603.09320)
• FAISS Wiki: Faiss Indexes (IVF, flat, PQ variants)
• Qdrant: What is HNSW?
• Pinecone Docs: Pod-based vs serverless indexes

Related reading on this site: B-Trees vs LSM-Trees: How Databases Choose Their Storage Engine and Oracle Database 23ai and the Oracle–Nvidia Partnership, which covers vector search built directly into a relational database engine.