Benchmarking Vector Indexes

How approximate nearest neighbor indexes are compared, and what the comparison shows for this unit's indexes. The four axes (recall, query cost, build cost and memory), operating points and the Pareto frontier, how the ANN-Benchmarks tool of Aumüller, Bernhardsson and Faithfull runs its experiments and what it found, then the unit's own indexes (k-d tree, locality-sensitive hashing, inverted file, product quantization, IVFADC and HNSW) measured on the same GloVe vectors over 30 seeds, how the picture changes with the size of the collection, and the measured size below which an exact scan is the right index, shown on this site's own passage vectors. Worked problems on frontiers, cost accounting and break-even sizes.

On 5,000 of this unit's GloVe vectors, the graph index of the HNSW article reaches a recall@10 of 0.9 with 716 distance computations per query, where the inverted file needs 1,157 and an exact scan 5,000. Is the graph therefore the better index? Its links take a third as much memory as the vectors, where the inverted file's structure takes 2.4 percent. It took 36 seconds to build, in the implementation used here, against 0.7. And on a collection of that size an exact scan answered in less than a tenth of a millisecond on the machine used, sooner than the inverted file did in all but one of 27 timed rounds. Which index is best depends on which of several quantities is scarce, and the answer changes with the size of the collection.

To benchmark an index is to measure the trade it offers: how much of the true answer it returns, against what a query costs, what the index costs to build, and how much memory it holds. No index has one number. Each has parameters that move it along a curve, and a comparison of two indexes is a comparison of two curves.

Here is the route. First we fix the four axes and the idea of an operating point and a frontier. Then we describe how the standard tool for this job, ANN-Benchmarks, runs its experiments and what its authors found, as their paper reports it. Next we compare every index of this unit on the same vectors. Then we follow the comparison across collection sizes, and find the size below which an exact scan beats the index, on this machine and in this implementation. The article assumes the earlier articles of the unit, whose indexes it compares: nearest neighbor search in high dimensions, locality-sensitive hashing, inverted file indexes, product quantization and HNSW. The numbers are computed by tools/experiments/vectors/benchmarking-vector-indexes.py.

Four axes

An approximate index gives up exactness to save work, so one number cannot describe it. The Faiss authors list the measures that matter as accuracy, search time, index building time and memory, and note that which of them constrain a system depends on the application: build time does not matter for an index that is built once and searched for years, and memory does not matter while the vectors fit many times over (Douze et al., 2026, sections 3.2 and 3.3). The ANN-Benchmarks tool records recall together with the size of the index, the time to build it, the time of a query and, where an implementation reports it, the number of distance computations (Aumüller, Bernhardsson, and Faithfull, 2020, Table 1). Both papers were read in their arXiv versions (2401.08281v4 and 1807.05614v2), and the section, table and figure numbers cited on this page are those versions'. This article uses the four axes in the following form.

  • Recall@10, the unit's measure of accuracy, defined in the first article: the share of the ten true nearest neighbors among the ten returned, averaged over the queries.
  • Query cost. The usual measure is queries per second (QPS), the number of queries answered in a second of wall-clock time. It is what a user of the index feels, and it depends on everything: the processor, the memory, the compiler, the care of the programmer. This unit's indexes are written in NumPy for reading, not for speed, and were measured on a shared machine. So the primary cost here is the count that does not depend on the machine, the number of distance computations per query, and wall-clock time is a secondary figure that is given in relative terms.
  • Build cost: the work of constructing the index, in distance computations and, secondarily, in seconds.
  • Memory: the bytes the index holds beyond the vectors, and whether it needs the vectors at all.

Operating points. Every index has parameters, and they are of two kinds. Build parameters fix the structure: the number of cells of an inverted file, the number of links per element of a graph. Query parameters can be changed for each query on a built index: the number of cells probed, the size of the candidate list. One setting of all the parameters, with the recall and the cost it produces, is an operating point. Sweeping a query parameter traces a curve of operating points for one built index, as the tables of the earlier articles did.

The frontier. An operating point is dominated if another point of the same index has at least its recall at no more than its cost, and is better in one of the two. The points that are not dominated form the Pareto frontier of the index: for each cost, the best recall the index can reach, and for each recall, the least it can cost. Comparing indexes means comparing frontiers. The Faiss authors define the same set, the settings that are the fastest for a given accuracy (Douze et al., 2026, section 3.4), and ANN-Benchmarks plots it by default.

The comparison below ends with an example of dominated points taken from its own numbers, and worked problem 1 computes a frontier by hand.

How ANN-Benchmarks is run

ANN-Benchmarks is a benchmarking tool for in-memory approximate nearest neighbor implementations, described by Aumüller, Bernhardsson and Faithfull (2020). This section reports its design as the paper gives it. The tool may have changed since the paper was written, and nothing here is a claim about its present state.

What is compared. The authors are explicit that they compare implementations, not algorithmic ideas: each library is installed as its authors publish it and run as intended, and two implementations of the same algorithm can perform differently. An implementation needs only a small programmatic interface, a call to build its structure from the data and a call to answer a query. All timing and all quality measures are computed by the framework from the returned neighbors, so that a new measure can be added without rerunning anything.

Data and truth. Each dataset is a file holding the data points, the query points, the distance measure, and the true 100 nearest neighbors of each query with their distances. Most datasets take a pseudorandomly selected ten thousand points out of the data as queries; others come with their own query sets. The paper's evaluation uses seven datasets (its Table 3), among them one million SIFT image descriptors of 128 dimensions under Euclidean distance and 1,183,514 GloVe word vectors of 100 dimensions under the angular distance. The GloVe set of this unit is another set of 100-dimensional GloVe vectors, 400,000 of them.

Recall by distance. Their recall counts a returned point as correct if its distance to the query is at most the distance of the true $k$th neighbor, which treats points at equal distances alike, and they also define an approximate version that accepts points within a factor $1 + \varepsilon$ of that distance. The first article compares these with the definition by identity that this unit uses; on data without ties the two agree.

Configurations. A configuration file lists, for each implementation, the build arguments and the query arguments to try. The framework expands their combinations. For each combination of build arguments it builds one structure, then runs the whole query set once for each combination of query arguments, so a built structure is reused across query settings.

The experiment loop. Each implementation runs in its own container, restricted by default to a single processor core, "since all implementations run on the same grounds". Queries are sent one at a time and timed individually. Memory is measured as the growth of the process while the structure is built. A run is stopped if it exceeds a time limit; in the paper's evaluation each parameter setting was given five hours to build and answer. A separate batch mode hands over all queries at once, which is how implementations on graphics processors are meant to be used, and its results are always shown apart from the others.

Presentation. The standard plot shows recall on the horizontal axis and queries per second, on a logarithmic scale, on the vertical, one line per implementation, each line being the Pareto frontier over all of that implementation's runs. Other plots relate recall to index size and to build time.

What the paper found. Its summary (section 4.5) is that graph-based implementations gave the best performance on most datasets, with HNSW often the fastest, at the price of long builds; that the inverted file index of Faiss was a suitable choice where a small and quickly built index is wanted; and that the standing of the implementations relative to each other was mostly stable across the standard datasets, with exceptions. Two of the exceptions concern indexes of this unit. On a synthetic dataset built so that every query has a few very close neighbors among points with no global structure, HNSW did not reach a recall above 0.86 at any tested setting, while the tree-based and the inverted file implementations found that data easy. And on one text-derived dataset the inverted file implementation did not exceed a recall of 0.7 at the tested settings. On build time, for an index reaching a recall of at least 0.9 on their GloVe data, the paper reports about 2 seconds for the inverted file and almost 5 hours for HNSW in one library, and adds that another library's implementation of HNSW built an index of that recall in 1,700 seconds (section 4.3). That last pair of numbers is the point about implementations in one line. The authors also observe that very few of the implementations can tune themselves to a requested recall, which leaves the user to search for a good setting.

Three features of that design carry over to any honest comparison, and the measurements below follow them: the truth is computed once by exact search and shared by all indexes; every index answers the same queries; and the result is a frontier per index, not a single point.

The unit's indexes on the same vectors

The comparison uses the 5,000 most frequent words of the unit's GloVe base set as the stored vectors, the unit's 1,000 queries, and the exact ten nearest neighbors of each query among those 5,000 as the truth. The size is set by the slowest build. The HNSW of its article is a Python loop around NumPy, one build of 5,000 vectors takes it half a minute or more on the machine used, and thirty builds of anything much larger were out of reach. Five thousand vectors is a collection that no one would index, and the section should be read for the shape of the frontiers and not as a case for indexing at that size. The next section follows the indexes that can be built at larger sizes.

Every randomized index is built 30 times, with seeds 0 to 29, and each figure is the median over the builds. The indexes and the parameter that moves each along its curve are these.

Index Built with Query parameter swept
k-d tree leaves of 16 vectors leaves opened before stopping (exact when unlimited)
LSH, random hyperplanes 64 tables of $r = 6$ or $r = 8$ bits tables used, 1 to 64
IVF-Flat $K = 71$ cells, about $\sqrt{5{,}000}$ cells probed $w$
Product quantization, re-ranked $M = 10$ sub-vectors, $k^* = 256$ short-list size $R$ re-ranked exactly
IVFADC, re-ranked $K = 71$ cells, the same quantizer on residuals $w$ and $R$
HNSW $M = 16$ links, efConstruction = 100 efSearch

The symbol $M$ means two different things in this table, as it does in the two papers: the number of sub-vectors of a product quantizer, and the number of links per element of the graph. The HNSW counts are not recomputed here. They are read from the runs made for the HNSW article, on the same 5,000 vectors with the same queries and the same 30 seeds. The k-d tree has no randomness and was run once, on the first 200 queries.

Counting the cost. A distance computation is one full 100-dimensional distance or dot product. For the scan that is $N$ per query. The other indexes are counted as their articles count them: the vectors compared for the k-d tree; the candidates plus the hyperplane dot products for LSH; the $K$ centroids plus the vectors on the probed lists for IVF-Flat; the distances evaluated during the walk for HNSW. The two compressed indexes need a convention, because most of their work is not distance computation. Building the lookup tables of a product quantizer is the arithmetic of $k^* = 256$ distances, and re-ranking $R$ candidates is $R$ more. Scanning a code is ten table reads and additions, where a distance is a hundred multiplications and additions. The tables below charge a scanned code as $M/m = 1/10$ of a distance computation and call the total distance-computation equivalents. That is fair as arithmetic. It is not a claim about time, since a table read and a multiplication do not cost the same on any machine, and several of the rankings below depend on the figure chosen. Write $c$ for the cost of a scanned code in distance computations. At its cheapest settings for the recalls 0.8, 0.9 and 0.95 of the table below ($R$ = 100, 200 and 500), re-ranked product quantization costs $356 + 5{,}000\,c$, $456 + 5{,}000\,c$ and $756 + 5{,}000\,c$. HNSW is the cheaper of the two only while $c$ is above 0.015, 0.052 and 0.094 at those three recalls, and IVF-Flat only while $c$ is above 0.056, 0.140 and 0.202. At a recall of 0.5 both are cheaper than the quantizer for every $c$. The convention $c = 0.1$ puts HNSW ahead of the quantizer at all four recalls, and puts the quantizer behind IVF-Flat at 0.8 and ahead of it at 0.9 and 0.95. The two closest calls are HNSW against the quantizer at 0.95 (break-even 0.094) and the quantizer against IVF-Flat at 0.9 (0.140). In this unit's NumPy code a scanned code cost about as much time as ten distances, not a tenth of one, as the last section reports. Every statement below about the two compressed indexes is a statement in this accounting.

Recall@10 against distance computations per query, on a logarithmic scale, for the indexes of the unit on 5,000 GloVe vectors: the Pareto frontier of each index, medians over 30 seeds. The dashed line is the cost of an exact scan. Read each curve from left to right as its query parameter grows. Notice the order at a recall of 0.9, which is HNSW, then re-ranked product quantization, then IVF-Flat in this accounting, where a scanned code counts as a tenth of a distance; that the order changes elsewhere (for a target between 0.919 and 0.947, the quantizer's point at 0.947 costs less than the graph's next point, at 0.959); that the two LSH curves and the stopped k-d tree stay far to the right of them, and that IVFADC passes the dashed line before it reaches a recall of 0.9.
Recall@10 against distance computations per query, on a logarithmic scale, for the indexes of the unit on 5,000 GloVe vectors: the Pareto frontier of each index, medians over 30 seeds. The dashed line is the cost of an exact scan. Read each curve from left to right as its query parameter grows. Notice the order at a recall of 0.9, which is HNSW, then re-ranked product quantization, then IVF-Flat in this accounting, where a scanned code counts as a tenth of a distance; that the order changes elsewhere (for a target between 0.919 and 0.947, the quantizer's point at 0.947 costs less than the graph's next point, at 0.959); that the two LSH curves and the stopped k-d tree stay far to the right of them, and that IVFADC passes the dashed line before it reaches a recall of 0.9.

The cheapest operating point of each index that reaches a given recall@10:

Index Recall 0.5 Recall 0.8 Recall 0.9 Recall 0.95
HNSW 157 (3.1%) 430 (8.6%) 716 (14.3%) 1,227 (24.5%)
IVF-Flat 254 (5.1%) 634 (12.7%) 1,157 (23.1%) 1,766 (35.3%)
Product quantization, re-ranked 776 (15.5%) 856 (17.1%) 956 (19.1%) 1,256 (25.1%)
LSH, $r = 6$ 1,396 (27.9%) 2,418 (48.4%) not reached not reached
IVFADC, re-ranked 1,140 (22.8%) 4,369 (87.4%) 8,574 (171.5%) 8,974 (179.5%)
k-d tree 5,000 (100%) 5,000 (100%) 5,000 (100%) 5,000 (100%)

Entries are distance computations per query, or equivalents for the two compressed indexes, with the share of an exact scan in parentheses. Each is the cost of the cheapest tested setting whose median recall reaches the target, so the recall actually obtained is somewhat above the target: 0.919 for HNSW at efSearch = 100, 0.907 for IVF-Flat at $w = 17$, 0.947 for product quantization at $R = 200$.

Several things can be read from the table and the figure.

  • The graph is cheapest at each of the four recall targets of the table, in this accounting, but not at every recall. At a recall of 0.9 HNSW computes 716 distances, a seventh of a scan, where IVF-Flat computes 1,157. Against IVF-Flat the comparison involves no convention. Against re-ranked product quantization it does at every target above 0.5, as the break-evens above show. Between the targets the tested settings are coarse, and the cheapest tested setting for a target recall changes hands several times. A target of 0.342 or less is met by one probe of IVF-Flat at 131 computations, or by a cheaper setting of another index for the lowest targets. Above it, reading "from $a$ to $b$" as a target above $a$ and at most $b$, the stored curves give: HNSW from 0.342 to 0.547, from 0.592 to 0.919, and from 0.947 to 0.959, where its runs stop at efSearch = 200; IVF-Flat from 0.547 to 0.592 (three probes, 254, against the graph's next setting at 270) and above 0.998; and re-ranked product quantization from 0.919 to 0.947, where HNSW's next setting costs 1,227 and the quantizer's 956, and from 0.959 to 0.998. This agrees in direction with what the ANN-Benchmarks paper found on much larger data with compiled implementations.
  • The inverted file is second among the indexes that keep the vectors, and its curve is smooth. Its recall is 0.342 with one probe at 131 comparisons and 0.8995 with 16 probes at 1,091, just short of 0.9, which it passes at 17 probes. Every operating point is reachable, one cell at a time.
  • Product quantization looks cheap and is not as cheap as it looks. Its 956 equivalents at a recall of 0.947 are 256 for the tables, 200 exact distances for re-ranking, and 500 for reading all 5,000 codes. The count has a floor: the 5,000 codes are read whatever the short-list size, so the index cannot go below 756 equivalents plus its short-list. IVF-Flat is cheaper up to a recall of 0.86 (12 probes, 830 computations), and HNSW up to its point at 0.919 and again from 0.947 to 0.959. Its strength is on another axis, memory, taken up below.
  • Hyperplane LSH needs a large share of the collection. With keys of six bits and all 64 tables it reaches a recall of 0.831 at 2,418 computations, nearly half a scan, and it does not reach 0.9 on the grid. With eight bits it stops at 0.466. The LSH article derives this from the angles between these vectors and their neighbors, and finds the same on the full set.
  • The k-d tree offers nothing between a poor answer and a scan. Stopped after 128 of its leaves it has compared 1,250 vectors and has a recall of 0.479. Run to the end it is exact and has compared all 5,000, which is the finding of the first article at this size too.
  • IVFADC is the worst index here, for a reason that is plain in the count. It builds a set of lookup tables for every probed cell, the arithmetic of 256 distances each, and a cell of this index holds about 70 vectors. Building the tables costs more than three times what comparing the query with the cell's vectors directly would. At 32 probes the tables alone are 8,192 computations, more than the scan. Jégou, Douze and Schmid (2011, section V.E) make a related remark about their own design: on small collections the fixed cost of the coarse step can dominate, and the plain asymmetric scan may then be preferred. The product quantization article describes the decomposition by which later implementations avoid recomputing the tables. The index is built for lists of thousands of codes, and a benchmark at the wrong scale shows it at its worst.

Example (a dominated point). IVFADC with 16 probes and a short-list of 500 has a recall of 0.899 at 4,769 equivalents. With 16 probes and a short-list of 200 it has 0.892 at 4,469. Neither dominates the other: the first has the better recall and the second the lower cost. But IVF-Flat with 17 probes has a recall of 0.907 at 1,157, which is better than both on both axes. Within IVFADC's own frontier the two points survive, and on a plot with IVF-Flat they are beside the point. A frontier describes one index, and the comparison is between frontiers.

Build cost and memory

Recall against query cost is two of the four axes. The other two, for the same indexes on the same 5,000 vectors:

Index Build work Memory beyond the vectors Needs the vectors
Exact scan none none yes
k-d tree sorting only, no distances 56,828 bytes yes
LSH, $r = 6$, 64 tables 1.92 million hyperplane dot products 1,498,928 bytes yes
IVF-Flat, $K = 71$ 7.5 million distances (21 passes of k-means) 48,976 bytes yes
Product quantization at most 26.9 million distance equivalents 152,400 bytes only to re-rank
IVFADC both of the above 201,376 bytes only to re-rank
HNSW, $M = 16$ 6.8 million distances 661,376 bytes yes

The vectors themselves take $5{,}000 \times 400 = 2{,}000{,}000$ bytes. The build work of k-means is the number of passes over the data times $N K$ distances; the product quantizer's is the same with $k^* = 256$ in place of $K$, in sub-vector arithmetic. The HNSW figures are medians over the 30 builds of its article.

Three points stand out. The inverted file is the smallest structure by far, 2.4 percent of the size of the vectors, and it builds with about as many distance computations as the graph. In wall-clock time the two builds are far apart on this machine, 0.7 seconds against 36, but that is a statement about implementations: k-means here is a few matrix products inside NumPy, and the graph build is a Python loop. The ANN-Benchmarks paper found the same order between compiled implementations, at 2 seconds against minutes or hours. The second point is that the graph's links take a third as much memory as the vectors they connect, and the 64 hash tables three quarters as much. The third is that the product quantizer is the only index in the table that can let go of the vectors. Its 152,400 bytes, of which 102,400 are the codebooks, replace 2,000,000, and at this size the codebooks are most of it. On the full base set the same quantizer takes 4.1 megabytes in place of 159.6.

How the picture changes with the size of the collection

An index is built to save work that grows with $N$, so its standing should improve as $N$ grows. The indexes that can be built quickly were run again on the 50,000 most frequent base words, with 30 seeds, and the inverted file and the product quantizer were measured on all 399,000 base vectors in their own articles. The table gives the cheapest tested setting that reaches a recall@10 of 0.9.

Base vectors $N$ IVF-Flat, $K \approx \sqrt{N}$ Product quantization, re-ranked HNSW
5,000 17 probes of 71 cells: 1,157 (23.1%) $R = 200$: 956 equivalents (19.1%) 716 (14.3%)
50,000 24 probes of 224 cells: 5,770 (11.5%) $R = 500$: 5,756 equivalents (11.5%) one build: 2,347 (4.7%)
399,000 19 probes of 632 cells: 15,259 (3.8%) $R = 1{,}000$: 41,156 equivalents (10.3%) not built

Entries are distance computations per query, or equivalents, with the share of a scan in parentheses. The three bases are nested, the queries are the same, and the truth is recomputed for each base, so the neighbors being sought differ from row to row: this is three related experiments and not one experiment scaled. The quantizer of the last row was trained on a sample of 50,000 vectors and reaches a recall of 0.942 at the setting shown; its next smaller short-list, 500, reaches 0.890. The HNSW entry at 50,000 is a single build with seed 0, made for the HNSW article and read from its results, at efSearch = 200 with a recall of 0.919; it has no spread to report and is not a median like the others.

  • The inverted file gains steadily. From 5,000 to 399,000 vectors the scan grows 80-fold and the inverted file's cost 13-fold. Its share of a scan falls from 23.1 percent to 3.8 percent. The cost model predicts growth as $\sqrt{N}$ at a fixed number of probes, about 9-fold here, and the number of probes needed for the same recall stayed within 17 to 24, so the model is roughly borne out.
  • The product quantizer's share stops falling near 10 percent. In this accounting it reads every code at a tenth of a distance, so it can never cost less than a tenth of a scan however large the collection. The quantizer alone does not prune. That is the job of the inverted file in front of it, in the combined index. IVFADC was not run at the larger sizes. The arithmetic moves in its favor as the lists grow and has not turned by 399,000 vectors: a list of 631 codes costs 63 equivalents to scan against 256 to build its tables, where a list of 70 cost 7 against the same 256. The table decomposition of Johnson, Douze and Jégou (2021), described in the product quantization article, removes most of the table cost, and was not implemented here.
  • Hyperplane LSH stays behind at the larger size. With keys of 12 bits and 64 tables on the 50,000 vectors it reaches a recall of 0.333 at 1,619 computations. The inverted file reaches 0.701 at 1,639.
  • The graph is nearly missing from the larger rows because it could not be built thirty times at those sizes in this implementation. Its one build of 50,000 vectors reaches a recall of 0.919 with 2,347 distance computations, 4.7 percent of a scan, less than half of what the inverted file needs there. This is the benchmark's own lesson about build cost: the index whose frontier is the best in the figure above, and in its single run at the next size, is the one that could not be included on equal terms.

When an exact scan is the right index

The unit's two small collections are 1,400 Cranfield abstracts and the 11,264 passages of this site's own pages, each encoded as a vector of 384 dimensions for the experiments of the previous unit. The site itself does not search by vectors. Its search is lexical, as how this search works describes, and the passage vectors are an experiment's encoding of the site as it stood at one commit. The question here is what a dense retrieval stage over those passages would need if the site added one. Does an index pay at that size? There are two answers, one in distance computations and one in time, and they differ.

In distance computations the index pays almost at once. An inverted file with $K = \lfloor \sqrt{N} \rfloor$ cells was built on each of the two sets with 30 seeds, and judged against exact search of the same vectors, with the 225 Cranfield queries and the 60 topical queries used in the site's dense-retrieval experiment.

Collection $N$ Cells $K$ Probes for recall@10 of 0.9 Distance computations Share of a scan
Cranfield abstracts 1,400 37 6 288 20.5%
Site passages (encoded for an experiment) 11,264 106 4 616 5.5%

On the site's passages four probes return 0.908 of the true ten neighbors for a twentieth of the comparisons, and eight probes return 0.957 for a tenth. These passage vectors are easier to partition than the word vectors: at a similar size, the 5,000 GloVe vectors needed 17 probes for the same recall. Passages of one page, or of pages on one subject, lie close together and fall into the same cells.

In time the answer depends on what a comparison costs beside everything else. The table gives the wall-clock time of one query, answered alone, for an exact scan and for an inverted file at the smallest number of probes whose recall@10 is at least 0.9. Both are written with the same NumPy operations, a matrix-vector product and a partial sort, and the inverted file stores its vectors grouped by cell. The index is the one built with seed 0, with $K$ the integer part of $\sqrt{N}$, which is why its probes and distance computations differ slightly from the 30-seed medians above. The two were timed alternately. One round times a pass of the scan over 200 queries (60 for the site's passages) and then a pass of the index over the same queries, for every collection in turn; there were three sessions of nine rounds, 27 rounds in all. The table gives the median time over the 27 rounds, the median and the range of the ratio of index time to scan time within a round, and the number of rounds in which the index was the faster.

Collection $N$ Dimensions Probes, distance computations Scan, ms Index, ms Index time over scan time: median (range) Rounds won by the index, of 27
Cranfield abstracts 1,400 384 5, 250 0.068 0.061 0.91 (0.69 to 1.81) 20
GloVe 5,000 100 17, 1,140 0.085 0.128 1.46 (0.87 to 2.51) 1
GloVe 10,000 100 21, 2,039 0.143 0.194 1.33 (0.99 to 2.21) 1
Site passages (encoded for an experiment) 11,264 384 4, 627 0.955 0.112 0.12 (0.08 to 0.19) 27
GloVe 20,000 100 18, 2,641 0.320 0.227 0.67 (0.47 to 1.47) 24
GloVe 50,000 100 24, 5,656 1.241 0.393 0.33 (0.24 to 0.43) 27
GloVe 100,000 100 30, 10,561 2.780 0.764 0.26 (0.19 to 0.38) 27
GloVe 399,000 100 18, 14,336 15.230 0.643 0.04 (0.03 to 0.06) 27

These times were taken on 17 November 2026 on a machine shared with other work: between 12 and 17 Python processes, nearly all of them other jobs, were running at the start and end of each session, and the matrix products were limited to four threads. The ranges show how much one round can differ from the next under that load. A single pass that is not interleaved is not reliable at the sizes where the two are close. Only what the 27 rounds agree on is stated below.

  • At 5,000 and 10,000 word vectors the scan is faster as well as exact. The index took about one and a half times as long at 5,000 and a third longer at 10,000, and won one round of 27 at each size, although it does 23 and 20 percent of the scan's distance computations. Its work is spread over a product with the centroids, a selection, and one small product per probed cell, and at this size the fixed cost of each step outweighs the arithmetic saved. One product over the whole collection is the fastest thing the machine can do with it.
  • From 50,000 word vectors the index is faster in every round, by a factor of three at 50,000 and of more than twenty at 399,000. At 20,000 it was faster in 24 rounds of 27, with a median ratio of 0.67 and single rounds as high as 1.47. So in these sessions the break-even for vectors of 100 dimensions lies between 10,000 and 20,000, and the upper end of that range is not far from even. The Faiss authors give the same order of magnitude as a rule of thumb: non-exhaustive search matters for collections larger than around ten thousand vectors, and their guide to choosing an index sends anything smaller to a flat index, an exact scan (Douze et al., 2026, section 5 and the decision tree of their appendix).
  • On Cranfield's 1,400 vectors neither is reliably faster. The index won 20 rounds of 27 with a median ratio of 0.91, and both take well under a tenth of a millisecond.
  • On the 11,264 passage vectors the index is faster in every round, and a scan would still be the right choice. With four probes the inverted file answers in 0.112 milliseconds where the scan takes 0.955, because these vectors partition well and each has 384 coordinates to multiply. But the scan's whole cost is about a millisecond. It is exact, where the index returns nine of ten neighbors. It needs no building and no rebuilding when pages change, where k-means on these vectors takes over a second and must be redone or patched as the collection moves. And it has no parameters to choose. At a millisecond per query there is little left to save.

So the measured answer has two parts. The size below which an exact scan was faster than this index, on this machine and in these sessions, is between 10,000 and 20,000 vectors of 100 dimensions, and lower for vectors of more dimensions that cluster well. The size below which an exact scan is the right choice is larger than that, because being faster by a millisecond buys nothing, and exactness, simplicity and the absence of a build are worth something. A dense retrieval stage over this site's eleven thousand passages, if the site had one, should be a scan. The question would be worth asking again at a few hundred thousand passages, where the table's last rows show a scan costing ten milliseconds or more and the index a fraction of one.

A caution belongs with the timings. The count of distance computations ranked the product quantizer well, and in NumPy its scan is slow: reading ten table entries for each of 399,000 codes took about 150 milliseconds per query in the product quantization experiment, where the exact scan of the same vectors takes 15 in the table above. That is about ten times as long for a scanned code as for a distance, against the tenth that the accounting of this article charges. The two were timed at different moments on a loaded machine, so the ratio is rough, but its direction is not in doubt: NumPy has a fast routine for a matrix product and none for table lookups. Compiled libraries implement the table scan with vector instructions of the processor (Douze et al., 2026, describe one such implementation). A distance-computation count is independent of the machine, and it is also blind to the difference between an operation the machine does well and one it does badly. That is the reason benchmarks of real systems report time, and the reason this article reports both.

What is proved here, what is cited, what the experiment shows

Proved or derived on this page. Nothing new is proved. The page uses, from the earlier articles, the fact that an index which re-ranks its candidates by exact distance returns a true neighbor exactly when it is among the candidates (Proposition 1 of the inverted file article), the cost model $K + wN/K$, and the identity that makes the asymmetric estimate of product quantization a sum of table entries. The break-even sizes of worked problem 3 are derived from the cost model.

Cited. The design and the findings of ANN-Benchmarks, from the paper of Aumüller, Bernhardsson and Faithfull (2020), read in its preprint version; the tool has changed since. The lists of trade-offs and the advice on small collections, from the Faiss paper (Douze et al., 2026). The HNSW measurements, from the HNSW article of this unit.

Measured. Every figure in the tables: medians over 30 seeds on subsets of one set of word vectors and on two small sets of text embeddings, with indexes written in NumPy. The distance-computation counts do not depend on the machine. The times do, and they also depend on the implementation to a degree that the counts hide: they were taken on a shared and loaded machine on 17 November 2026, in three sessions of nine alternating rounds, and are reported with their ranges. None of this ranks the methods in general. It shows how the comparison is made and what it gave here.

Worked problems

These problems are posed on the measurements of this article. The script recomputes every number.

Problem 1 (a frontier by hand). Five operating points of the IVFADC index on the 5,000 vectors are given as (recall@10, equivalents): A (0.781, 2,269), B (0.795, 2,369), C (0.615, 4,289), D (0.787, 4,319), E (0.861, 4,369). Which are on the Pareto frontier of these five?

Sort the points by cost, which is the order given, and walk through them keeping the best recall seen so far. A point is on the frontier exactly when its recall is higher than that of every cheaper point.

Point Cost Recall Best recall among cheaper points On the frontier
A 2,269 0.781 none yes
B 2,369 0.795 0.781 yes
C 4,289 0.615 0.795 no: B is cheaper and better
D 4,319 0.787 0.795 no: B is cheaper and better
E 4,369 0.861 0.795 yes

The frontier is A, B, E. The points C and D are settings no one should use: they probe 16 cells with a short-list too small to hold the neighbors those cells contain, and B, with 8 probes and a longer short-list, does better for nearly half the cost. A benchmark that reported only C for this index would have understated it, and one that reported only E would have hidden that most of E's cost buys little over B. That is why a comparison shows the frontier.

Problem 2 (accounting for a compressed index). On the full base set of 399,000 vectors, product quantization with $M = 10$ and $k^* = 256$ reaches a recall@10 of 0.942 when the 1,000 best by estimate are re-ranked, and the inverted file with 632 cells reaches the same recall with 32 probes and 24,902 distance computations. Compare the two in distance-computation equivalents and in memory.

The product quantizer builds its tables at the cost of 256 distances, re-ranks 1,000 candidates exactly, and reads all 399,000 codes at a tenth of a distance each:

$$256 + 1{,}000 + \frac{399{,}000}{10} = 41{,}156 \text{ equivalents},$$

10.3 percent of a scan. The inverted file spends 24,902, or 6.2 percent. By this count the inverted file does 60 percent of the work of the quantizer for the same recall, and the quantizer's work is almost all in reading codes.

Memory goes the other way. The inverted file must hold the vectors, 159.6 megabytes, with 1.85 megabytes of its own. The quantizer's codes and codebooks take 4.1 megabytes. It needs the vectors only for the 1,000 it re-ranks, and those can be read from slower storage. So the answer depends on which axis is short. If the vectors fit in memory, the inverted file is cheaper to search. If they do not, the quantizer is the index that still works, and the combination of the two, the IVFADC of the product quantization article, is the design built for that case at a scale where its lists are long enough to pay for their tables.

Problem 3 (a break-even size from the cost model). Under the equal-lists model, an inverted file with $K = \sqrt{N}$ cells and $w$ probes costs $(1 + w)\sqrt{N}$ distance computations. Above what collection size is that less than a scan, for $w = 4$ and for $w = 17$? Why is the size at which an index pays off in practice so much larger?

With $K = \sqrt{N}$ the cost is $K + wN/K = \sqrt{N} + w\sqrt{N} = (1 + w)\sqrt{N}$. It is below $N$ when $(1 + w) < \sqrt{N}$, that is, when

$$N > (1 + w)^2 .$$

For $w = 4$, the number of probes that reached a recall of 0.9 on the site's passage vectors, the break-even size is 25 vectors. For $w = 17$, the number that reached it on the 5,000 GloVe vectors, it is 324. By the count of distance computations an inverted file is ahead of a scan for any collection worth the name.

In practice the size is much larger, for the reasons the timing table shows. The count treats a comparison with a centroid, a comparison with a vector on a list, and a comparison in a scan as the same thing, and leaves out the selection of the cells and the handling of the lists. In the measurements of this article the inverted file became faster than a scan somewhere between 10,000 and 20,000 vectors of 100 dimensions on the machine used, thirty to sixty times the model's 324. And the model says nothing about the value of an exact answer or the cost of building and maintaining the index, which is what decides the matter for a collection of eleven thousand passages.

What we have learned

An index is described by a frontier of operating points on four axes: recall, query cost, build cost and memory. ANN-Benchmarks fixes the truth by exact search, gives every implementation the same queries on one processor core, and plots each implementation's frontier of recall against queries per second; its authors found graph indexes fastest on most data and slowest to build, and found exceptions. On 5,000 GloVe vectors the unit's graph index reached a recall of 0.9 with 716 distance computations and the inverted file with 1,157. Re-ranked product quantization needed 956 equivalents in an accounting that charges a scanned code a tenth of a distance, and its place between the other two at that recall holds only while that charge is between 0.052 and 0.140. In that accounting the graph was the cheapest at each recall target of the comparison, but not at every recall: for targets between 0.919 and 0.947 the quantizer was. Meanwhile hyperplane hashing and the k-d tree stayed near the cost of a scan and IVFADC, built for long lists, exceeded it. The inverted file's share of a scan fell from 23 percent at 5,000 vectors to 3.8 percent at 399,000, and the product quantizer's stayed near a tenth while its memory was a fortieth of the vectors'. In wall-clock time on the machine used, over 27 alternating rounds, the inverted file overtook an exact scan between 10,000 and 20,000 word vectors. Over the 11,264 passage vectors that an experiment made of this site, a scan takes about a millisecond and is exact, and that is what a dense stage over them should use; the site's own search is lexical and has no such stage.

That closes the unit on vector search. The indexes here find the nearest vectors to a query vector. Whether the nearest vectors are the right passages is a question about the vectors, and what to do with the passages once found is a question about ranking: neural ranking and hybrid retrieval takes the short list that a first stage returns and ranks it with a model that reads the query and the passage together.

References

  • Aumüller, M., Bernhardsson, E., and Faithfull, A. (2020). ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87, 101374. record · 3 pages
  • Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., and Jégou, H. (2026). The Faiss library. IEEE Transactions on Big Data, 12(2), 346–361. arXiv:2401.08281. record · 4 pages
  • Jégou, H., Douze, M., and Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 117–128. record · 6 pages
  • Johnson, J., Douze, M., and Jégou, H. (2021). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535–547. record · 3 pages