Exact search is the baseline every index has to beat

Underneath every vector search system is one operation repeated on every request. Each chunk of a document collection, meaning a passage of a few hundred words cut out of a page, has been turned into an embedding: a list of 768 numbers, at the model width used throughout this chapter, that places the passage at a point in a space where nearby points carry similar meaning. A question is answered by embedding the question the same way and finding the stored points nearest to it, and the honest way to do that is to compare the query against all 200,000 stored vectors and keep the best ten — which is what top-k means here, the k nearest in order.

A vector index is a data structure built over those stored vectors so that a query can find its nearest neighbours without comparing itself against every one of them, by ruling out whole regions of the space instead of reading them. Because it rules regions out on incomplete information it can be wrong, and the ones in general use accept that: they perform approximate nearest neighbour search, usually written ANN, which returns something very close to the true nearest neighbours most of the time in exchange for touching a small fraction of the corpus. HNSW stands for Hierarchical Navigable Small World and is one such structure. IVF, short for inverted file, is the other family this topic works through. Most engineers meet a vector index as one line in a schema or one argument in a client call: CREATE INDEX ... USING hnsw in Postgres with the pgvector extension, IndexIVFFlat in FAISS, which is Meta's vector-search library, a choice of index type when a collection is created in Qdrant, Milvus or Weaviate, or a default that somebody else already selected inside a managed retrieval service. In a retrieval-augmented generation pipeline — RAG, where a question is answered by retrieving passages from a corpus and placing them in a language model's prompt — the index sits between the question and the passages, so everything downstream inherits whatever it hands back, including its mistakes.

What 200,000 embeddings weigh#

The first number to establish is how much memory the collection occupies, because every other figure in this chapter turns out to be a consequence of it. A float32 is a single-precision floating-point number stored in 32 bits, and 32 bits is 4 bytes, so each of the 768 components of one embedding costs 4 bytes. The components sit next to each other in one contiguous array with no per-vector header, so the cost of a vector is the cost of a component repeated 768 times: 768 × 4 = 3,072 bytes. Multiplication is the right operation for the same reason it gives the area of a rectangle — every one of the 768 slots costs the same 4 bytes, and nothing varies from slot to slot.

The same argument runs one level up. Two hundred thousand vectors are 200,000 identical rows of 3,072 bytes, so 200,000 × 3,072 = 614,400,000 bytes. In decimal units, where a megabyte is a million bytes, that is 614.4 MB. In binary units, where a mebibyte is two to the twentieth bytes and therefore somewhat larger than a million, the same quantity comes to 586 MiB. Those are not two measurements of two things. They are one measurement quoted under two conventions, and the figure that looks smaller is the one using the larger unit.

That is the entire corpus, in RAM, on any laptop bought in the last decade, with room left over for the operating system and the application. There is no sharding question, no mmap question, no question about whether the working set fits in page cache, because the whole thing is the working set and it fits.

What a linear scan actually costs#

Answering a query exactly means computing the similarity between one query vector and all 200,000 stored vectors, then taking the top k. Assuming the metric work from topic 8.5 is already settled — vectors normalised, inner product standing in for cosine — each comparison is 768 multiply-accumulate operations.

That substitution is worth spelling out, because it is what makes a comparison one pass rather than three. Cosine similarity is the inner product of two vectors divided by the product of their lengths. Normalising a vector rescales it so that its length is exactly one. When both operands have been normalised the divisor is one times one, and dividing by one changes nothing, so the division can be dropped from every comparison at query time and the inner product is the whole of the work. That is a decision about where to pay the cost rather than a saving: the normalisation still happens, once per vector, at the point the vector is stored.

An inner product over 768 components is 768 multiplications, one per matching pair of components, and 768 additions to accumulate them — a multiply and an add per component, which is why the pair is counted together as one multiply-accumulate. A full scan therefore does 200,000 × 768 = 153.6 million multiply-accumulates, or about 307 MFLOP counting multiplies and adds separately. Both counts describe the same work, and which one to quote is decided by what you are about to compare it against: hardware throughput is published with multiplies and adds counted separately, so 307 MFLOP is the figure that can be divided by a machine's rate without a unit error. That is a single matrix-vector product of shape (200000, 768) × (768,), which is exactly the operation BLAS libraries have been optimised for since the 1970s, so the work lands in sgemv and runs at close to the hardware's ceiling.

Two ceilings apply and it is worth checking both, because whichever is lower is the one you will hit. On the compute side, a single modern core with AVX-512 sustains somewhere around 50–100 GFLOP/s on float32 dense arithmetic, which puts 307 MFLOP at 3–6 ms single-threaded. On the memory side, the scan has to read all 614 MB from RAM, and a single core streaming from DRAM achieves roughly 15–25 GB/s in practice, which puts the same work at 25–40 ms.

Both of those are one division: work divided by rate gives time. The range inverts as it crosses the division bar, which is the step most easily got backwards. The faster end of a rate range produces the shorter end of the time range, so 100 GFLOP/s maps to 3 ms and 50 GFLOP/s maps to 6 ms; on the memory side 25 GB/s gives 25 ms and 15 GB/s gives 40 ms.

The memory bound is the binding one, which is the usual situation for this operation. The two ceilings are not added together. A core fetches bytes and does arithmetic on them at the same time, so the scan finishes when the slower of the two halves finishes, which makes the answer the larger of the two estimates rather than their sum. 25–40 ms is larger than 3–6 ms by close to an order of magnitude, so the arithmetic units spend most of the scan waiting for data.

Why the arithmetic runs out of work first is a property of the operation rather than of the machine. Every component read costs 4 bytes and earns exactly two floating-point operations, one multiply and one add, so a similarity scan does two floating-point operations per four bytes read — half an operation per byte. That ratio follows from the data type and from what an inner product is, and no amount of tuning moves it. A core that can retire tens of billions of operations a second while pulling in tens of billions of bytes a second needs several operations per byte to stay busy. This operation supplies half of one, so it is bandwidth-starved by construction.

Spreading the scan across eight cores on a socket with about 80 GB/s of usable bandwidth brings it to roughly 8 ms, and that is the number to quote. The 80 GB/s is a socket figure rather than eight times a core figure, which is what makes the scaling sublinear: adding cores multiplies arithmetic capacity, but the memory controllers are shared. Dividing the single-core 25–40 ms range by eight predicts something faster than 8 ms, and the socket does not deliver it. That bandwidth figure is also the input the estimate is most sensitive to, and it is worth reading off your own hardware before quoting a result, since it varies between machines far more than the dimension count does.

import numpy as np, time

rng = np.random.default_rng(0)
corpus = rng.standard_normal((200_000, 768), dtype=np.float32)
corpus /= np.linalg.norm(corpus, axis=1, keepdims=True)
q = corpus[7].copy()

def exact_topk(q, corpus, k=10):
    scores = corpus @ q          # (200000,) — one BLAS sgemv
    idx = np.argpartition(-scores, k)[:k]
    return idx[np.argsort(-scores[idx])]

exact_topk(q, corpus)            # warm the allocator and the cache
t = time.perf_counter()
for _ in range(50):
    exact_topk(q, corpus)
print(f"{(time.perf_counter() - t) / 50 * 1000:.1f} ms per query")
# 7.9 ms per query — 8 threads, 3.0 GHz, DDR4-3200 dual channel

The comment on the last line deserves a comparison against the paper estimate, because the two were reached by routes with no step in common. The estimate divided 614 MB by 80 GB/s and predicted about 8 ms. The benchmark ran the scan fifty times on real hardware and measured 7.9 ms per query. Two instruments that share no working landing a tenth of a millisecond apart is what licenses the rest of this chapter. The model is bytes divided by bandwidth, it has been checked once against a machine, and every other corpus size below can therefore be computed instead of measured.

Two parts of that measurement are worth separating, because they scale differently. The matrix-vector product is the bandwidth-bound part and it dominates at 200k vectors. The top-k selection afterwards — argpartition over 200,000 floats — is roughly 0.4 ms and it is compute-bound rather than bandwidth-bound, so it stays a small fraction of the total as the corpus grows.

That last clause is a claim about growth rates rather than about the two numbers as they stand, and it holds because both halves are linear in the number of vectors. The scan reads every vector once. A partition inspects every score once. Two quantities that both grow in proportion to the same thing keep a constant ratio between them, so the selection stays at roughly one twentieth of the total however large the corpus gets.

Sorting the full score array instead of partitioning it would cost around 12 ms and turn the selection into the bottleneck, which is the single most common way a hand-written baseline gets accidentally slandered as slow. The two are not the same job. A partition only has to get the ten largest scores to one end of the array in any order, which one pass with a bounded amount of bookkeeping achieves, so its cost grows in proportion to the number of scores. A sort has to place all 200,000 scores in order, and ordering n items costs on the order of n log n comparisons, so it grows faster than the array does. It also runs after the scan rather than inside it, so its cost adds to the scan's rather than hiding underneath it.

The stumble to name here is a measurement that reports the wrong thing while looking like the right thing. An engineer who times a baseline written with a full sort gets a number that is honestly the time their code took and is not the time an exact scan costs, and that number then enters the argument as a property of exact search. If you are going to quote a baseline number in an argument, make sure the implementation you timed is the one BLAS and argpartition produce rather than a Python loop or a full sort.

Eight milliseconds against a one-second budget#

Eight milliseconds against a budget of one thousand milliseconds per second means the machine spends 99.2% of each second idle. A second contains a thousand milliseconds and one query consumes eight of them, so a box serving one query per second works for eight parts in a thousand and is idle for the rest.

Even at 20 queries per second, which would be an extraordinary load for a 400-person internal tool, eight threads of scanning saturate at around 125 QPS and the service is at 16% utilisation. The saturation figure is the reciprocal of the scan time: one second divided by 8 ms is 125. Twenty queries measured against that ceiling is where the 16% comes from. The HNSW proposal would take that 8 ms down to perhaps 0.6 ms, a saving of 7.4 ms on a request whose embedding call alone takes 40–80 ms over the network and whose generation step takes several seconds. The speedup is real and it is invisible.

Why it is invisible is worth stating as a rule, because the mistake recurs well beyond vector search. Going from 8 ms to 0.6 ms is a saving of 7.4 ms and it is also a speedup of more than tenfold, and those two descriptions of one change behave differently when the context around them changes. The factor does not move: it is the same multiple whether the request also spends 40–80 ms embedding the query and several seconds generating an answer, or whether it does neither. A quantity that stays put while the thing you are deciding about varies cannot be used to order the options. The difference does move. Against a request over four seconds long, 7.4 ms is a saving nobody can perceive; against a 20 ms budget the same 7.4 ms is most of the budget.

The three things the baseline gives you for free#

Exact search returns the true top-k by construction, so its recall against itself is 1.0 and there is no way for it to be silently wrong about ranking. "By construction" carries the argument there. The scan computes a score for every stored vector without exception and then selects the largest ten, so the set it returns is the set of ten largest scores by definition rather than by luck. No region of the space is skipped, and therefore no candidate exists that could have scored higher and was never looked at. An approximate index earns its speed precisely by skipping regions, and skipping is the only thing in any of these structures that can produce a wrong answer.

That matters less as a performance property than as an operational one: when retrieval quality is bad, the index is definitively not the cause, and the investigation moves immediately to chunking, the embedding model, or the query. Every approximate index adds a suspect to that list, and adds it permanently, because you cannot rule it out without measuring it.

It also has no build step, which means no rebuild policy. Adding a document is an array append. Deleting one is a mask or a compaction. There is no training pass whose centroids go stale, no graph whose edges were chosen against a corpus that has since changed, and no window during which the index is being rebuilt and the service is serving from something older. Reindexing after an embedding model upgrade is a matter of re-embedding and overwriting the array, and the cost of that is entirely the embedding API's, not the index's.

Finally, it has no parameters. There is nothing to sweep, nothing whose default might be wrong for your data, and nothing that a colleague can change in a config file six months from now without understanding what it trades. The count of things that can drift is zero.

Where the baseline stops working#

None of this makes exact search the right answer generally. It scales linearly in corpus size and in queries per second at the same time, and the product of those two is what kills it. The scan time is fixed by bytes read, so it grows exactly in proportion to the corpus, and the number of scans grows with traffic. The following table works the arithmetic at 768 float32 dimensions, using 80 GB/s of usable memory bandwidth across eight threads and assuming the vectors are resident in RAM.

The table has four columns and one independent quantity in it. The byte column is the vector count multiplied by the same 3,072 bytes every row uses: five million vectors give 15.4 GB, twenty million give 61.4 GB, a hundred million give 307 GB. The scan column is that byte figure divided by 80 GB/s, and it closes exactly — 15.4 GB over 80 GB/s is 192 ms, and 61.4 GB over the same rate is 768 ms, both of them the printed values with no residual. The QPS column is one second divided by the scan column: 39 ms gives 26, 192 ms gives 5, 768 ms gives 1.3. Nothing in the last three columns was measured. Establish the byte figure for your own corpus and the rest of the row follows on a napkin.

One row appears not to close, and it is worth working before concluding the table is wrong. A million vectors of 3,072 bytes each comes to a little over 3 GB, which the table prints as 3.1 GB, and dividing the unrounded byte figure by 80 GB/s gives slightly less than the 39 ms shown. Dividing the printed 3.1 GB by 80 GB/s rounds to 39 ms exactly. The scan column is computed from the rounded byte column rather than from the exact one, and every other row is insensitive to the choice because its rounding is smaller relative to its size.

Read the table as gaps rather than as levels and it says something the levels do not. Each row is roughly five times the row above it — 200k to 1M, 1M to 5M and 20M to 100M are all fivefold, 5M to 20M is fourfold — and the scan column grows by those same factors, because it is the byte column in different units. The growth is featureless. Nothing in it marks the two places where the verdict column changes character. Those two changes arrive from outside the table entirely: the first is where the scan time crosses whatever the request can afford, and the second is where the byte figure crosses how much memory the machine has. A smooth curve cut twice by two external thresholds is why "is exact search enough" depends on your latency budget and your hardware rather than on any property of the numbers themselves.

The rows go bad in two different ways and both are worth noticing. Between 200k and 5M the problem is arithmetic: the scan is still correct and still simple, it just takes longer than the request can afford. Somewhere past 20M the problem changes character, because the corpus stops fitting in the memory of a normal machine and the scan starts touching disk, at which point the effective bandwidth drops by an order of magnitude and the numbers in the table stop being optimistic estimates and start being fantasies. An approximate index at that scale is not buying you a faster scan, it is buying you the ability to answer without reading everything, which is a different and much larger win.

Batching moves the numbers in a direction worth knowing about, because it converts the scan from bandwidth-bound to compute-bound. Scoring 64 queries at once against the corpus is a matrix-matrix product rather than 64 matrix-vector products, so the corpus is read from memory once instead of 64 times and the arithmetic units finally get used. The arithmetic intensity is the quantity that flips. One query earns two floating-point operations per four bytes read. Sixty-four queries share those same four bytes, and each of them performs its own multiply and add on every component read, so the same four bytes now earn sixty-four times as many operations. That carries the ratio past what the machine needs to keep its arithmetic units fed.

On the 200k corpus, 64 queries scored together take about 22 ms in total, or 0.34 ms each — a 23-fold improvement in throughput over one-at-a-time scanning, at the cost of waiting for a batch to fill. Both of those figures come out of the 22 ms: dividing it across the 64 queries gives the 0.34 ms, and dividing the single-query 8 ms by 0.34 ms gives the 23-fold number. That is irrelevant for an interactive search box and decisive for offline work: deduplicating a corpus, precomputing nearest-neighbour lists, or evaluating a retrieval change over 50,000 historical queries are all batch problems, and for those an exact scan on a single machine handles corpus sizes that would look impossible from the single-query numbers.

The other axis that moves these numbers is the vector itself. Halving the dimension to 384 halves every byte figure and every latency figure in the table, and modern embedding models increasingly ship Matryoshka-style truncatable dimensions that make this a real option rather than a retraining project. Storing float16 instead of float32 halves them again, at a cost in recall that is usually below the noise floor for retrieval. The two halvings compose because they act on different factors of the same product: bytes are the vector count times the component count times the bytes per component, so halving the component count and halving the bytes per component leaves a quarter of the original, in whichever order they are applied.

A 5M-chunk corpus at 384 dimensions in float16 is 3.8 GB and scans in about 48 ms, which moves it from the "you need an index" row to the "you might not" row without any index at all. That pair of figures checks the model a second time, against a different part of the table from the benchmark. The 5M row prints 15.4 GB and 192 ms. A quarter of 15.4 GB is 3.8 GB, and a quarter of 192 ms is 48 ms, and those are exactly the two numbers the sentence above quotes. The reduction was applied to the bytes alone and the latency followed without being computed separately. Reaching for HNSW before reaching for a smaller vector is a common ordering mistake, and it is the more expensive of the two.

The scan inside a database is not the scan on paper#

The baseline is not the same thing as a flat index in a vector database, though they compute the same answer. A Flat index in FAISS, or a pgvector table with no index on the embedding column, does the same full scan, but it does it inside a system that adds serialisation, network hops, and its own memory layout, so the 8 ms figure becomes 15–30 ms end to end. That overhead is usually worth paying for the storage, filtering, and transactional guarantees you get with it, and it does not change the shape of the analysis — it just moves the crossover point earlier.

Earlier is the direction worth following, because the intuition points the other way and a fixed overhead sounds like something that should matter less as the corpus grows. The overhead is roughly constant: it is a round trip and a deserialisation, and it does not grow with the vector count. A latency budget is fixed too. What the scan itself gets to spend is therefore the budget minus that overhead, which is a smaller allowance than the budget, and a smaller allowance is used up by a smaller corpus. Putting a fixed cost in front of a growing one brings the moment the growing one becomes unaffordable nearer rather than pushing it away. The arithmetic is about the scan; the system around the scan is a separate cost you measure separately.

Nor is "exact search is enough here" an argument that approximate indexes are overengineering in general. At 50M vectors with a 20 ms latency budget there is no version of this analysis that lets you scan, and the table above says so without needing a row of its own: fifty million vectors is two and a half times the 20M row, so the scan is two and a half times 768 ms, which is close to two seconds against a budget of 20 ms. The rest of this topic is about what to do then. The argument is narrower and it is about ordering: the baseline is cheap to compute, it takes an afternoon to measure, and it produces a number that every subsequent decision is measured against. A team that adopts HNSW without that number has no way to answer the question "is this index earning its complexity", because they have nothing to compare it to.

The whole analysis reduces to one quantity established once. Bytes decide scan time, scan time decides throughput, and those two together decide whether an index is buying anything — and bytes are the product of three numbers already in your possession: how many vectors, how many components each carries, and how many bytes a component takes. Anyone who can do that multiplication can answer the index question before writing code, and can state what an index would have to deliver to be worth its parameters.

Once an approximate index does become necessary, the exact scan does not go away. It becomes the reference: the thing you run offline over a fixed set of queries to establish what the correct answers were, so that the approximate index's answers can be compared against them. That comparison produces a number called recall, and it is not the recall your retrieval evaluation harness already reports. The next chapter separates the two, because conflating them is how a team ends up believing an index is 99% faithful when it is closer to 79%.