Dense retrieval and HNSW

Comparing a lexical retriever against a dense one requires knowing the dense side at the level needed to run it rather than to design it, which is four steps with no branches in them. Every chunk goes through an embedding model once at index time, producing a fixed-length float vector. The vectors are stored. At query time the query goes through the same model, and the system returns the chunks whose vectors are nearest by cosine similarity or inner product.

The word vector index names the structure that makes the last step tractable by giving up exactness, and it is where all the operational consequences live. An exhaustive comparison against every stored vector is exact and, past a certain size, unaffordable; an approximate index trades a small and measurable amount of recall for two or three orders of magnitude less work. The dominant approximate structure is a navigable graph, and a graph has a memory profile that a postings list does not.

The four steps, at the level required to run them#

from sentence_transformers import SentenceTransformer
import numpy as np

model = SentenceTransformer("BAAI/bge-large-en-v1.5")   # d = 1024

chunks = load_chunks()                                   # 4.4M strings
vecs = model.encode(chunks, batch_size=256,
                    normalize_embeddings=True)           # (4_400_000, 1024) f32

q = model.encode(["max_connections"], normalize_embeddings=True)
scores = vecs @ q.T                                      # cosine, since normalised
top = np.argpartition(-scores[:, 0], 10)[:10]

Normalising the vectors makes the dot product equal to the cosine, which is why production systems almost always store unit vectors and use inner product — it removes a division from the inner loop. The dimension is a property of the model and not a choice you make at query time; 384, 768, 1024 and 1536 are the common ones, and some models support truncating the vector at the cost of a few points of recall.

Three things about that indexing pass cause silent damage and none of them raise an error. The model has a maximum sequence length — 512 tokens for most BERT-derived encoders — and input beyond it is truncated rather than rejected, so a 900-token chunk is embedded from its first 512 tokens and the rest of the text is represented by nothing at all. Chunks must fit the model, and checking that the chunker's token budget is below the encoder's limit is a two-line assertion worth writing down.

Many models are also asymmetric, expecting a different prefix on queries than on documents. The bge family wants queries prefixed with Represent this sentence for searching relevant passages: and documents left bare; e5 wants query: and passage:. Omitting the prefix at query time does not fail, it just quietly costs two to five points of recall, and because the system still returns plausible results nobody investigates. The third is version drift: query and corpus vectors must come from the same model weights, so a model upgrade invalidates every stored vector at once, and running a new model against an old index produces results that are wrong in a way that looks like ordinary mediocrity.

The one-off cost of the pass itself is modest and worth having a number for. At a mean chunk length of 380 tokens, 4.4 million chunks is roughly 1.7 billion tokens; a 1024-dimension encoder on a single A10G-class GPU processes them at something like 1,800 chunks per second with batching, which is about 40 minutes of GPU time. On a hosted embedding API priced around $0.02 per million tokens it is roughly $34. Neither number is the reason people hesitate to re-embed — the six-hour index rebuild that follows it is.

All three of those figures come from one multiplication or one division each, and doing them is what makes the paragraph a budget rather than a reassurance. Four point four million chunks at a mean of 380 tokens is a little under 1.7 billion tokens. Four point four million chunks at 1,800 a second is a little under two and a half thousand seconds, which is the 40 minutes. And 1.7 billion tokens is seventeen hundred millions of tokens, so at two cents a million the bill is a little under $34. The useful thing about laying them out this way is seeing which input each figure is sensitive to: the GPU time depends on the chunk count and not on how long the chunks are, while the API bill depends on the token total and not on how the chunks were cut. Halving the chunk size doubles the first and leaves the second alone.

That code is correct and unusable at scale. vecs @ q.T reads the entire matrix: 4,400,000 vectors at 1024 dimensions and four bytes per dimension is 4,096 bytes each, or 18.0 GB per query. At 25 GB/s of achievable memory bandwidth that is 720 ms of pure streaming, before any thought about the arithmetic, and it is 720 ms for every single query regardless of how many results you want. Exhaustive search is the right answer up to something like 100,000 vectors and wrong above it.

Both halves of that are one step. A float32 is four bytes and there are 1024 of them per vector, so a vector is 4,096 bytes; 4.4 million of those is a little over eighteen thousand million bytes, which is the 18.0 GB. Then divide the bytes by the bandwidth: eighteen gigabytes at 25 GB/s is a little over seven tenths of a second, which is the 720 ms. What the division makes plain is that the figure is a floor rather than an estimate. It assumes the arithmetic is free, the memory system delivers its full rated bandwidth, and nothing else is running. Anything real is slower. It also explains why asking for fewer results does not help: the scan has to look at every vector to know which ten are nearest, so the work is set by the collection and not by k.

What HNSW does instead, and what that costs#

HNSW — Hierarchical Navigable Small World — builds a multi-layer graph over the vectors. Every vector is a node in layer 0; each node is also promoted to higher layers with exponentially decreasing probability, so layer 1 might hold 270,000 nodes and the top layer a few dozen. Within each layer, nodes are connected to roughly M near neighbours plus a few deliberately long-range links, which is what makes the graph navigable in a small number of hops.

Those layer sizes are not arbitrary and knowing where they come from makes the structure predictable. A node is promoted to the layer above with a probability of about one in M, so each layer holds roughly an M-th of the one below it. With M at 16 and 4.4 million nodes at the bottom, layer 1 holds around 270,000 — which is the figure quoted — layer 2 around seventeen thousand, and after four or five such divisions the top layer is down to the few dozen a search can enter at. The number of layers therefore grows with the logarithm of the collection, which is the same reason the search is fast: each descent narrows the search region by a factor of M before the expensive part begins.

A search enters at the single top-layer entry point, greedily walks to the nearest node in that layer, descends, repeats, and at layer 0 runs a best-first search maintaining a candidate list of size ef_search.

The traversal touches on the order of 1,200 to 4,000 nodes for ef_search = 64 on a collection this size, which is 0.05 percent of the 18 GB an exhaustive scan reads. That is the whole benefit, and it comes with one property that governs everything about deployment: the address of the next node is not known until the current node has been read. The graph is a pointer-chasing structure, so each hop is a dependent random access, hardware prefetching cannot help, and readahead has nothing to read ahead to.

Fifteen hundred dependent random reads from RAM, at roughly 80–100 ns of latency each plus the cost of the distance computation, come to a few milliseconds. The same fifteen hundred reads from NVMe, at 100 µs each because they cannot be issued in parallel, come to 150 ms and upward, and once queues and cache misses compound the figure keeps climbing. There is no configuration that fixes this, because the dependency chain is what the algorithm is.

Splitting those two figures into their parts shows why the same hop count behaves so differently in the two places. Fifteen hundred reads at a hundred nanoseconds apiece is a hundred and fifty microseconds — a seventh of a millisecond, which is nothing. The few milliseconds in RAM are therefore almost entirely the distance computations, since every hop compares the query against each of a node's neighbours across all 1024 dimensions, and that arithmetic is what the CPU is actually spending its time on. Now move the same fifteen hundred reads to NVMe. A hundred microseconds each is a thousand times the RAM latency, so the read term becomes 150 ms and the arithmetic term stays where it was. The component that was invisible becomes the entire cost, and it does so without the algorithm changing at all — which is why the same code, the same parameters and the same collection can differ by three orders of magnitude on one property of the machine.

The memory bill follows directly. For hnswlib the per-element cost is the vector plus the layer-0 neighbour lists plus a label:

per element  =  d * 4          (vector, float32)
             +  M * 2 * 4      (layer-0 links; layer 0 uses 2M)
             +  8              (external label)

d = 1024, M = 16  ->  4096 + 128 + 8  =  4,232 bytes
4.4M elements     ->  18.6 GB resident, plus ~0.3 GB for upper layers

Every line of that sum is checkable and the total closes against a figure computed a different way. The vector is 1024 dimensions at four bytes, which is 4,096. Layer 0 gives each node twice M links at four bytes a link, which with M at 16 is 128. Add the eight-byte label and an element is 4,232 bytes; 4.4 million of them is 18.6 GB. Compare that against the 18.0 GB the exhaustive scan reads, which was the vectors alone. The difference is a little over half a gigabyte, and spread across 4.4 million elements that is precisely the 128 bytes of links plus the 8 of label — the two calculations agree, and the agreement is the check that neither of them dropped a term. It also settles what the graph costs over simply storing the vectors: about three percent. The graph is not expensive. Requiring it to be resident is.

-- pgvector, the same structure with the same requirement
CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 200);

SET hnsw.ef_search = 64;   -- per-session recall/latency dial

ef_construction controls how much work index building does to find good neighbours and affects build time far more than query time; building this index takes roughly 4 to 9 hours on 16 cores and is not incremental in any useful sense. ef_search is the dial at query time: raising it from 40 to 200 typically moves recall@10 from about 0.93 to about 0.99 and multiplies latency by three, because it is directly proportional to how many nodes the traversal visits. That the parameter goes up by five while latency goes up by three is the useful part of the number rather than a discrepancy in it. A query costs a fixed amount — embedding the text, descending the upper layers, assembling the response — plus a variable amount proportional to the layer-0 traversal. Multiplying only the variable half by five multiplies the total by less than five, and how much less tells you what fraction of the query was fixed to begin with. On a system where raising ef_search fivefold barely moves latency at all, the traversal is not where the time is going and tuning it will not help.

M is the parameter with consequences in three directions at once, which is why it is the one to set deliberately rather than by default. Raising it from 16 to 48 gives each node more neighbours, so the greedy walk has better options and recall at a fixed ef_search improves by several points; it also triples the neighbour-list memory from 128 bytes per node to 384, adding 1.1 GB on this collection, and it slows construction because every insertion evaluates more candidate edges. Higher M pays off on high-dimensional data and on collections with clustered structure, and is close to wasted on 384-dimension vectors over uniform text. The default of 16 is a reasonable starting point and the sweep — build at 16, 32 and 48 on a 10 percent sample and measure recall against exact results — takes an afternoon of machine time and settles it for the life of the index.

Why the lexical index does not have this problem#

A postings list is a sorted, delta-encoded, block-compressed array laid out contiguously on disk. Walking it is a sequential read, the next block's address is known before the current one is decoded, and the operating system's readahead has been optimising exactly this access pattern since the 1970s. An index larger than RAM works fine because the hot terms stay in page cache — the memory the kernel keeps recently read file blocks in on behalf of every process — and the cold ones cost one or two sequential reads, which NVMe serves at gigabytes per second.

The two rows near the bottom of that table are the same fifteen hundred hops counted in different units, and checking that they agree is worth a moment. Fifteen hundred nodes at 4,232 bytes each is a little over six megabytes, which is the "bytes touched per query" entry, and it is the same six megabytes the scenario below describes a machine reading off disk four kilobytes at a time. One figure came from the per-element formula and the other from watching a process, and they land on the same number. Set that beside the lexical row: 40 KB on a query with a rare term, up to 9 MB on a pathological one, and the difference is that the lexical figure is set by what was typed while the dense figure is set by a configuration parameter. A user cannot make a dense query cheap by typing something more specific.

That is the asymmetry you can rely on without benchmarking anything: the vector index needs its graph in memory, and the lexical index can serve from page cache. It is a statement about data structures rather than about any particular implementation, so it holds across pgvector, Qdrant, Weaviate, Milvus and a raw hnswlib process.

Approximation, quantisation, deletions and filters#

HNSW is approximate, and it is worth being precise about what that means: at ef_search = 64 roughly 5 percent of queries will miss at least one of the true top 10, and the misses are not random — they concentrate on vectors in sparse regions of the space, which are disproportionately the unusual documents. A retrieval system can be losing 5 percent of its true nearest neighbours silently, and the only way to know is to compute exact results on a sample and compare.

Two different quantities travel under the word recall in that paragraph and the one above it, and confusing them is the commonest way to misread an ANN benchmark. One is the share of the true top ten that came back, averaged over queries. The other is the share of queries that got the complete top ten with nothing missing. The second is always the smaller, and if misses fell independently it would be very much smaller — ten chances to lose one item leave far fewer than nineteen queries in twenty intact. So a figure of five percent of queries missing at least one is only consistent with a per-item recall in the nineties if the misses are strongly clustered inside a minority of queries. Which is exactly what the sentence above says happens: they concentrate on vectors sitting in sparse regions. The two numbers do not conflict, and the reason they do not is the same fact that makes the losses matter — the queries that lose neighbours lose several at once, and they are the unusual queries.

The memory claim is specific to graph-based indexes with full-precision vectors, and there are two escape hatches. Quantisation shrinks the vectors: scalar quantisation to int8 cuts 4,096 bytes to 1,024 and costs about one point of recall; binary quantisation with a rescoring pass over the top few hundred candidates cuts it to 128 bytes and can hold recall above 0.90 on many collections, which takes 18.6 GB down to roughly 1.2 GB. That last figure is the per-element sum run again with one term changed. Binary quantisation stores one bit per dimension, and 1024 bits is 128 bytes, so an element becomes 128 for the vector plus the same 128 of links plus the same 8 of label, which is a shade over two hundred and sixty bytes — and 4.4 million of those is the 1.2 GB. Notice what happened to the proportions. At full precision the links were three percent of the element; after binary quantisation they are almost half of it, so shrinking the vectors further would buy progressively less. The structure that was a rounding error has become the thing you are paying for. Disk-native designs change the structure instead: DiskANN's Vamana graph is built with a much larger degree and laid out so that a search issues far fewer, larger, batchable reads, keeping only a compressed copy of the vectors in memory. Either of those makes an SSD-resident vector index viable, and both are additional systems to operate and additional recall to account for.

Two other properties matter operationally and are easy to discover the hard way. Deletions in HNSW are tombstones — the node stays in the graph, the traversal still walks through it, and reclaiming the space requires a rebuild, so a collection with high churn slowly accumulates dead nodes that cost latency. And filtered search, where you want the nearest neighbours among documents matching a predicate, interacts badly with graph traversal: if the filter is selective, the greedy walk spends most of its hops on nodes that fail the filter and recall collapses, which is why engines implement pre-filtering with a bitmap or fall back to exhaustive scan below a selectivity threshold. Both of those follow from one property of the graph, which is worth extracting because it predicts the next surprise as well as these two. The edges of an HNSW graph are what makes any node reachable from the entry point, and they were chosen from vector proximity alone. Deleting a node would break every path that routed through it, and the traversal has no way to repair a path at query time, so the node has to stay and be skipped — which is why space is only reclaimed by rebuilding. Filtering breaks the same guarantee from the other direction. Restricting the answer to documents matching a predicate means walking a graph whose edges were built without any knowledge of that predicate, so the surviving nodes may not be connected to each other at all; the greedy walk then wanders through nodes that fail the filter and terminates somewhere unhelpful. That is why recall collapses rather than degrading gently. A lexical index handles the same filter as one more postings list to intersect, and it can do that because intersecting two sorted lists yields a sorted list — the structure is closed under the operation, so nothing is broken by applying it.

Dense retrieval is cheap to describe and expensive to provision, and the two facts are connected: the four-step description hides the fact that step four is a pointer-chasing graph traversal whose working set is the whole index. Size the machine from d × 4 bytes per chunk plus M × 8 bytes of links before benchmarking anything, treat ef_search as the recall dial and M as a build-time commitment, and check the truncation limit and the query prefix, because both fail silently and both look like ordinary mediocrity.

With both structures understood at this level, the comparison between them stops being a matter of opinion. It becomes three measurements over one corpus, and those three do not move together.