# How Vector Search Actually Works: IVF and HNSW > Source: > Published: 2026-07-09 16:00:00+00:00 Every system that does "semantic" anything — RAG pipelines, recommendation engines, image search, dedup — boils down to one operation: *given this vector, find the closest ones out of millions.* The vectors are embeddings, a few hundred to a couple thousand numbers each, and "closest" means closest in meaning. You'd assume the database either scans all of them (slow but correct) or uses some clever tree to jump straight to the answer. It does neither. Instead it deliberately settles for the *approximately* closest vectors — and that compromise is the entire reason vector search is fast enough to exist. Two algorithms do almost all the heavy lifting in practice, in pgvector, Qdrant, FAISS, and the rest: **IVF** and **HNSW**. Here's what they're actually doing under the hood, and how to choose between them. The natural objection is: why approximate? Just find the real nearest neighbor. In two or three dimensions you could — a k-d tree or similar structure prunes away big regions of space and finds the true closest point quickly. The trouble is that embeddings live in *hundreds* of dimensions, and high-dimensional space is deeply weird. It's called the **curse of dimensionality**. As dimensions grow, the distance to your nearest point and the distance to your farthest point drift toward being almost the same. Formally, the contrast `(d_max − d_min) / d_min` shrinks toward zero. When everything is roughly equidistant from everything else, a tree can't confidently say "skip this whole branch, it's too far" — the bounding regions all overlap, every branch looks plausible, and the search degrades into checking nearly everything. Exact indexes quietly collapse back into brute force. So we change the question. Instead of "prove you found *the* nearest," we ask "quickly find something *very probably* among the nearest." That's **approximate nearest neighbor** (ANN) search, and it swaps a guarantee for speed. The quality knob becomes **recall**: of the true top-k neighbors, what fraction did we actually return? Every algorithm below is a different strategy for getting high recall without looking at the whole dataset, and every one has a dial that trades recall for speed. Before the algorithms, one detail: what does distance even mean here? Three measures dominate. **L2** (Euclidean) is straight-line distance and is affected by both a vector's direction and its length. **Inner product** rewards vectors that point the same way *and* are long, so it's sensitive to magnitude. **Cosine similarity** ignores length entirely and measures only the angle between vectors — which is why it's the usual default for text embeddings, where direction carries the meaning and length is noise. The useful fact: if you normalize all vectors to unit length (a common preprocessing step), these collapse into each other — inner product equals cosine, and L2 becomes a simple function of cosine. So a lot of systems normalize once up front and stop worrying about which metric they're using. With that settled, the algorithms only need one primitive: "how far apart are these two vectors?" The **Inverted File Index** is the simpler of the two, and its idea is one you'd come up with yourself. Before any queries, cluster the entire dataset into `nlist` groups using k-means — an algorithm that repeatedly assigns each point to the nearest cluster center, then recomputes each center as the average of its members, until things stop moving. Each cluster gets a centroid, and every vector is filed under its nearest centroid. Those per-cluster lists are the "inverted lists"; together they're the inverted file. Now a query comes in. Instead of comparing it against millions of vectors, you compare it against the handful of centroids, pick the `nprobe` closest ones, and search *only* inside those clusters. You've replaced "check everything" with "check the few neighborhoods the answer is most likely to be in." ``` build: k-means(all vectors, nlist) → centroids + a vector-list per centroid query: find the nprobe centroids nearest the query search only the vectors in those nprobe clusters return the top-k closest of those ``` Two parameters run the show. `nlist` is how many clusters you carve the space into; `nprobe` is how many of them you actually search per query. Turn `nprobe` up and you examine more neighborhoods, so recall climbs — but you're doing more work, so latency climbs too. That single dial is the recall-versus-speed tradeoff, exposed. There's a refinement worth knowing because it shows up everywhere. Searching the probed clusters by brute force (FAISS calls this "IVF,Flat") still compares full vectors. To go faster and use far less memory, you can compress the stored vectors with **Product Quantization**: chop each vector into several sub-vectors, run k-means on each slice to build a small "codebook," and store only the index of the nearest codebook entry per slice. A 128-dimension float vector can shrink to a handful of bytes. Distances are then computed against these compressed codes using precomputed lookup tables — the asymmetric variant (keep the query full-precision, only the stored vectors are compressed) is the accurate, popular choice. That's "IVF,PQ," and it's how billion-scale indexes fit in memory. The **Hierarchical Navigable Small World** graph has become the default in many vector databases because it delivers the best recall for a given speed — at a memory cost. Its idea is different and rather elegant: build a graph where each vector is a node connected to some of its nearest neighbors, and stack that graph in layers. The top layer is sparse — only a few nodes, with long-range links. Each layer down has more nodes and shorter links, and the bottom layer contains every vector. Searching means entering at the top, greedily hopping toward the query through the sparse long-range links to get into the right *region* fast, then descending a layer and repeating with finer resolution, until the bottom layer pins down the precise neighbors. It's exactly how you navigate to an address: find the city, then the district, then the street, then the house — each step a zoom-in. ``` search: start at the top-layer entry point on each layer: greedily walk to whichever neighbor is closer to the query when you can't get closer, drop down a layer and continue on the bottom layer, collect the ef_search best candidates → top-k ``` HNSW has three knobs. `M` is how many neighbors each node keeps per layer — higher means a richer graph, better recall, and more memory. `ef_construction` is how hard the build works to find good neighbors when inserting nodes (build quality). `ef_search` is the size of the candidate list kept during a query: turn it up and recall improves at the cost of speed — the same dial IVF has, by another name. The algorithm comes from a 2016 paper by Malkov and Yashunin, and it has aged remarkably well. You will almost never implement either of these — you'll choose an index type and tune its knobs in a database that already has them. So the practical question is which to reach for: | IVF (+PQ) | HNSW | | |---|---|---| | Core idea | Cluster the space; search a few clusters | Layered proximity graph; navigate down to the answer | | Memory | Low (especially with PQ compression) | High — the graph and its edges are big | | Recall at a given speed | Good | Best in class | | Build cost | Cheap (one k-means pass) | Higher (incremental graph construction) | | Scales to billions | Yes — its main strength | Harder; memory and build cost grow uncomfortably | | Main tuning knobs | `nlist` (clusters), `nprobe` (clusters searched) | `M` (neighbors), `ef_construction` (build), `ef_search` (query) | | Updates | Adding many vectors eventually wants re-clustering | Inserts naturally; deletes are awkward | The short version: **HNSW if you want the best speed-recall tradeoff and can afford the RAM**, which describes most small-to-medium collections — and it's why so many systems default to it. **IVF, usually with PQ, when the dataset is enormous or memory is tight**, where its low footprint and clean scaling win even though you fiddle with `nprobe` to claw recall back. These aren't academic curiosities; they're the index types sitting behind tools you may already use. In Postgres, the `pgvector` extension offers exactly these two: an `ivfflat` index (set the number of `lists` at build time and `probes` at query time) and an `hnsw` index (set `m` and `ef_construction` at build, `ef_search` at query). Qdrant is built around HNSW. FAISS — the library underpinning a huge amount of this — implements IVF, PQ, HNSW, and combinations, and its index "factory" strings (`IVF4096,PQ64` , `HNSW32` ) are just these building blocks composed. What that means in practice is that the knobs above are the levers you'll actually pull. Recall too low? Raise `nprobe` or `ef_search` . Index too big for RAM? Move to IVF with PQ, or lower `M` . Builds too slow on a huge dataset? IVF's single clustering pass beats rebuilding a giant graph. You're not inventing the algorithm; you're deciding how much accuracy to trade for how much speed and memory — which is the same decision the algorithm designers made, handed to you as configuration. The knobs only help if you know which way to turn them, and the honest answer is you measure. The standard method: take a sample of real queries, compute their *true* nearest neighbors by brute force once (slow, but it's offline and one-time), and treat that as ground truth. Now run your index at various `nprobe` or `ef_search` values and compute recall — what fraction of the true top-k each setting returns — alongside the query latency. You get a recall-versus-latency curve, and you pick the point that meets your recall target at acceptable speed. This is exactly how public ANN benchmarks work, and it's worth doing on *your* data, because the right setting depends on your embeddings' distribution, not on someone else's blog post. Guessing `ef_search = 100` because it worked for somebody is how you end up either slow or silently missing results. Here's a problem that ambushes nearly everyone eventually: you don't just want "nearest vectors," you want "nearest vectors *where category = invoices* and *date > January*." Combining a metadata filter with ANN is genuinely hard, and it's worth knowing why before it bites you. There are two naive strategies, both flawed. **Post-filtering** runs the normal vector search, then throws away results that don't match the filter — simple, but if the filter is selective you can ask for the top 10 and get back 2, because the other 8 got filtered out. **Pre-filtering** finds the matching rows first, then searches only those — correct, but it can wreck the index: an HNSW graph built over the whole dataset may have no usable path through just the surviving nodes, and an IVF probe may find its clusters mostly emptied by the filter. This is why modern vector databases put real engineering into *filtered* search (filter-aware graph traversal, or keeping the candidate pool large enough to survive filtering). When you evaluate a vector DB, how well it does filtered search is often a bigger deal than its raw ANN speed. A reminder before you reach for a fancy index: if your collection is small — a few thousand vectors, even tens of thousands — just compare against all of them. A brute-force (flat) scan is *exact*, has zero build cost, never goes stale, and on modern hardware is plenty fast at that size. ANN indexes earn their complexity only once a linear scan actually hurts; adding HNSW to a 5,000-row table is pure downside. And when you go the other direction — past what fits in RAM — IVF and HNSW aren't the end of the story either: on-disk graph indexes like DiskANN target billion-scale datasets that can't live in memory, and approaches like ScaNN and the older locality-sensitive hashing occupy other corners of the same tradeoff space. IVF and HNSW are the two you'll meet first and most often, not the only two that exist. Strip away the clustering and the graph layers and IVF and HNSW are the same bet: *don't prove you found the best match — quickly get somewhere almost certainly excellent, and stop.* High-dimensional space makes the exact answer prohibitively expensive, so both algorithms spend their cleverness on candidate generation: IVF narrows by carving space into neighborhoods and visiting the promising few; HNSW narrows by walking a map that zooms from continents to street corners. Once you see vector search as "approximate on purpose," the knobs stop being mysterious — every one of them is just you, telling the index how much of the true answer you're willing to miss in exchange for an answer right now.