The word neighborhood is one of this unit's 1,000 query vectors, and its ten nearest neighbors among the 399,000 GloVe word vectors of the base set are neighborhoods, neighbourhood, suburb, downtown, residential, area, suburban, city, town and apartment. Exact search finds them with 399,000 distance computations. An index that first divides the base set into 632 cells finds nine of the ten with 1,019: 632 to find the cell whose center is nearest the query, and 387 for the vectors in that cell. The tenth, apartment, is in the next cell over. How are the cells made, how much of the true answer is lost for a given amount of work, and can the index ever know that it has lost nothing?
An inverted file index for vectors (IVF) partitions the base vectors into cells, keeps for each cell the list of the vectors in it, and answers a query by comparing it with the vectors of the few cells nearest to it. The cells come from k-means: each vector belongs to the cell of its nearest centroid. The index is approximate. A true neighbor that lies in a cell the search did not open is never seen.
Here is the route. First we see the whole idea on six points on a line, taken from the course. Then we define the structure and the search, and prove that the recall of a search is a simple count: the share of the true neighbors that lie in the cells it opened. Next we work out what a search costs and why the number of cells is set near $\sqrt{N}$. Then we measure recall against the number of cells opened on the GloVe vectors, compare k-means cells with the random leaders of the course's cluster pruning, and look at where the missed neighbors are. Finally we derive a bound that can prove an answer exact, and measure how rarely it does. The article assumes the k-means algorithm and builds on the cluster pruning of clustering and the cluster hypothesis. Recall@$k$ and the dataset are defined in nearest neighbor search in high dimensions. The numbers are computed by tools/experiments/vectors/inverted-file-indexes-for-vectors.py, with the index itself in ivf.py beside it.
The idea on six points
The course article on the cluster hypothesis solves, as its worked problem 2, a small exercise that is already an inverted file index. Six documents lie on a line at 0, 1, 2, 4, 5 and 9, in two clusters $A = \{0, 1, 2\}$ and $B = \{4, 5, 9\}$ with centroids 1 and 6. Every document is in the cluster of its nearer centroid, so this is a clustering k-means could return.
A query arrives at 3.4. The index compares it with the two centroids first: it is at distance 2.4 from the centroid of $A$ and 2.6 from the centroid of $B$. It then opens the nearer cell only, compares the query with the three documents of $A$, and returns the document at 2, at distance 1.4. The true nearest document is the one at 4, at distance 0.6. It is in $B$, and the search never looked there.
The work was five comparisons in place of six: two centroids and three documents. The answer was wrong. If the search opens both cells it compares the query with everything, eight comparisons, and returns the document at 4. That is the whole trade in miniature. The index saves work by not looking in most cells, and it is wrong exactly when a true neighbor lies in a cell it did not look in. The rest of the article puts numbers on both sides for a collection large enough that the saving is worth having.
The structure and the search
The index has two parts, built once.
- A coarse quantizer. Choose a number of cells $K$ and run k-means on the base vectors, or on a sample of them, to get centroids $\vec c_1, \dots, \vec c_K$. Cell $i$ is the set of all points of $\mathbb{R}^m$ nearer to $\vec c_i$ than to any other centroid. The k-means article shows that each cell is convex, an intersection of half-spaces bounded by the planes that bisect the segments between centroids. "Quantizer" is the term of product quantization: a function that replaces a vector by one of finitely many representatives, here its nearest centroid.
- The inverted lists. Assign every base vector $\vec x_n$ to its nearest centroid, and store with each cell $i$ the list $L_i$ of the vectors assigned to it. The lists are disjoint and together hold all $N$ vectors. Write $n_i$ for the length of $L_i$.
A query $\vec q$ is answered in three steps, with a parameter $w$, the number of cells to probe:
- compute the distance from $\vec q$ to all $K$ centroids;
- take the $w$ nearest centroids and read their lists;
- compute the distance from $\vec q$ to every vector on those lists and return the $k$ nearest.
The index of the opening has $K = 632$ and probed $w = 1$ cell.
The name comes from text retrieval. An inverted index maps each term to the list of documents that contain it, and a query reads only the lists of its own terms. Sivic and Zisserman (2003) carried the structure over to image descriptors. They clustered the descriptor vectors of video frames with k-means, called each cluster a visual word, and kept an inverted file from visual words to the frames in which they occur, so that frames could be retrieved "in the manner of Google". Jégou, Douze and Schmid (2011, section IV) made it an index for nearest neighbor search among the vectors themselves. In their design the k-means quantizer is the coarse quantizer, each list stores its vectors in compressed form, and a query is assigned to its $w$ nearest centroids instead of one, because, as they observe, a query and its nearest neighbor "are often not quantized to the same centroid, but to nearby ones". The compressed lists are the subject of the next article. Here the lists hold the vectors themselves, the variant usually called IVF-Flat. In the Faiss library the two parameters are named nlist and nprobe (Douze et al., 2026, section 5.1). That paper was read in its arXiv version (2401.08281v4), and its section and equation numbers on this page are that version's.
The course met the same design before any of this, as cluster pruning: pick $\sqrt{N}$ documents at random as leaders, attach every other document to its nearest leader, and at query time score only the followers of the nearest leader or leaders. The cluster hypothesis article describes it from the course text (Manning, Raghavan, and Schütze, 2008, section 7.1.6) and measures it on Cranfield, and computing vector scores compares it with other shortcuts. An inverted file index is cluster pruning with the leaders replaced by k-means centroids. A later section measures what that replacement is worth.
The memory needed beyond the vectors is small: $K$ centroids of $m$ numbers each, and one identifier per vector to say which list it is on. For $K = 632$ and the GloVe vectors that is $632 \times 100$ numbers of four bytes and 399,000 identifiers of four bytes, about 1.85 megabytes beside the 159.6 megabytes of the vectors.
What a search returns
How good is the answer? Recall@$k$, the unit's measure, is the share of the true $k$ nearest neighbors that appear among the $k$ returned. For this index it can be computed without running a search at all.
Here is the idea in one sentence: inside the cells it opens, the index computes exact distances, so it makes no mistakes about the vectors it sees, and its only mistakes are the neighbors it never sees.
Proposition 1. Suppose no two base vectors are at the same distance from the query. A search that probes a set $P$ of cells and returns the $k$ nearest vectors on their lists returns a true $k$-nearest neighbor of the query if and only if that neighbor lies in a cell of $P$. Its recall@$k$ is the number of true $k$-nearest neighbors lying in the cells of $P$, divided by $k$.
Proof. Let $\vec x$ be one of the $k$ nearest base vectors to $\vec q$. At most $k - 1$ base vectors are nearer to $\vec q$ than $\vec x$ is. The candidates, the vectors on the probed lists, are a subset of the base vectors, so at most $k - 1$ candidates are nearer than $\vec x$. If $\vec x$ is itself a candidate, it is therefore among the $k$ nearest candidates, and step 3 returns it. If $\vec x$ is not a candidate, step 3 cannot return it. So the returned true neighbors are exactly the true neighbors that are candidates, and those are the true neighbors lying in cells of $P$. Recall@$k$ counts them and divides by $k$.
Two consequences follow at once.
- Recall never falls as $w$ grows. The $w + 1$ nearest cells include the $w$ nearest, so the count in the proposition can only grow.
- Probing every cell is exact search. With $w = K$ every base vector is a candidate, and the recall is 1. The cost is then $K + N$ comparisons, more than the exact search it reproduces.
The proposition also says what to measure. For each true neighbor of each query, find the cell it lies in, and find that cell's rank among the cells ordered by the distance of their centroids from the query. Call it the neighbor's cell rank. The neighbor is returned exactly when $w$ is at least its cell rank. The whole curve of recall against $w$ comes from one table of cell ranks, and the script computes it that way. It also runs real searches for $w = 1$, 8 and 64 on 200 queries and checks that they return the same counts, and that $w = K$ returns the exact answer.
Back to the opening. For neighborhood and the index with 632 cells:
| True neighbor | Distance | Cell rank |
|---|---|---|
| neighborhoods | 0.582 | 1 |
| neighbourhood | 0.635 | 1 |
| suburb | 0.731 | 1 |
| downtown | 0.742 | 1 |
| residential | 0.754 | 1 |
| area | 0.770 | 1 |
| suburban | 0.773 | 1 |
| city | 0.780 | 1 |
| town | 0.784 | 1 |
| apartment | 0.798 | 2 |
The nearest cell holds 387 vectors; the six nearest its centroid are downtown, city, york, philadelphia, boston and richmond, so it is a cell of place words. Nine of the true ten are in it, and the recall@10 with one probe is 0.9. The search fills the tenth place with suburbs, the next-nearest vector in that cell. The second-nearest cell holds 448 vectors around room, empty, bathroom and kitchen, and apartment is there. With $w = 2$ the recall is 1, at $632 + 387 + 448 = 1{,}467$ comparisons.
Not every query is so well served. The query epidemic has the true neighbors outbreak, cholera, pandemic, epidemics, disease, plague, flu, outbreaks, hiv and influenza. Its nearest centroid, at distance 0.860, belongs to a cell of 385 words about hardship (exacerbated, upheaval, hardship, cutbacks). None of the ten neighbors is in it. Eight are in the second cell, a cell of disease names whose centroid is at distance 0.863, and two in the third. With one probe the index returns famine, alarming, scourge, crisis and six more words of that kind, a recall of 0. With three probes it is exact. The two centroids differ in distance by 0.003, and the query sits almost on the boundary between their cells.
What a search costs
The cost of a search is counted in distance computations, the unit's measure that does not depend on the machine. Step 1 makes $K$ of them and step 3 makes one for every vector on the probed lists:
$$\text{cost} = K + \sum_{i \in P} n_i .$$
Here is the idea of the cost model in one sentence: more cells make each list shorter but make the first step longer, so there is a best number of cells, and it grows as the square root of the collection.
The derivation. Suppose the lists were all the same length, $N/K$. Then a search with $w$ probes costs
$$f(K) = K + \frac{wN}{K}.$$
The first term grows with $K$ and the second shrinks. By the inequality between the arithmetic and geometric means, $K + wN/K \ge 2\sqrt{K \cdot wN/K} = 2\sqrt{wN}$, with equality exactly when the two terms are equal, $K = wN/K$. So
$$K^* = \sqrt{wN}, \qquad f(K^*) = 2\sqrt{wN}.$$
For the GloVe base set, $N = 399{,}000$ and $\sqrt{N} = 631.7$. With one probe the best whole number of cells is 632, and the model's cost is $632 + 399{,}000/632 = 1{,}263$ comparisons, 0.32 percent of an exact search. A quarter as many cells, $K = 158$, gives $158 + 2{,}525 = 2{,}683$, and four times as many gives $2{,}528 + 158 = 2{,}686$: the cost roughly doubles in either direction. This is why this article's main index has 632 cells, and why the course's cluster pruning takes $\sqrt{N}$ leaders. The authors of Faiss write the same formula and its minimum at $K = \sqrt{wN}$, and remark that this is where the usual recommendation of a number of lists proportional to $\sqrt{N}$ comes from (Douze et al., 2026, equation 18 in section 5.1 of the arXiv version; the sentence as printed there names the number of probes where the formula before it requires the number of lists). They add that it is a rough guide, for three reasons: the number of probes has to grow with the number of lists to hold the accuracy fixed, the lists are not balanced, and large systems do not compare the query with every centroid.
Unbalanced lists cost more when queries follow the data. The model assumed equal lists, and real lists are unequal. If queries fall into cells in proportion to the cells' sizes, the inequality works against the search on average, because a query is then more likely to land in a large cell than a small one. Suppose a query lands in cell $i$ with probability $n_i/N$. The expected length of the list it reads is then
$$\sum_{i=1}^{K} \frac{n_i}{N} \cdot n_i = \frac{1}{N} \sum_{i=1}^{K} n_i^2 = I \cdot \frac{N}{K}, \qquad I = \frac{K}{N^2} \sum_{i=1}^{K} n_i^2 .$$
The number $I$ is called the imbalance factor (Douze et al., 2026, section 5.1). It is 1 for equal lists and larger otherwise: Problem 3 of the cluster hypothesis article proves that $\sum_i n_i^2 \ge N^2/K$ with equality exactly for equal sizes, and that is the statement $I \ge 1$. Worked problem 4 below computes it for a small case.
The condition matters. Queries that are not distributed like the base vectors can land in small cells more often than in large ones, and then unequal lists cost less than equal ones. This unit has an example. The index over the 5,000 most frequent words in the benchmarking article has 71 cells and an imbalance factor of 1.17, so equal lists would hold 70.4 vectors and size-proportional queries would read 82.6 on average. The unit's queries, which are words of every frequency, read 60.1 with one probe. On the full base set of this article, where queries and base vectors are drawn from the same 400,000 words, the size-proportional prediction is close, as the next section shows.
Jégou, Douze and Schmid's own measurements show the effect of unequal lists. On their set of 1,000,991 image descriptors with 1,024 cells, one probe scanned 1,947 codes on average (their Table V), where equal lists would hold 978.
Recall measured on GloVe
Proposition 1 turns recall into a count, and the count has to be measured: nothing in the construction says how many true neighbors share the query's cell. The experiment uses the unit's dataset as its first article sets it up: 399,000 GloVe word vectors of 100 dimensions scaled to unit length (Pennington, Socher, and Manning, 2014), 1,000 further vectors held out as queries, and the exact ten nearest neighbors of each query as the truth. For each index, k-means is run for 20 iterations on a sample of 100,000 base vectors, from seeds drawn at random, and every base vector is then assigned to its nearest centroid. The sample and the seeds change with the random seed; there are 30 seeds, and each figure below is the median over them with the first and third quartiles in parentheses.
| Cells probed $w$ | Recall@10 | Recall@1 | Distance computations | Share of a full scan |
|---|---|---|---|---|
| 1 | 0.436 (0.432 to 0.437) | 0.494 | 1,438 | 0.36% |
| 2 | 0.575 (0.570 to 0.579) | 0.637 | 2,249 | 0.56% |
| 4 | 0.702 (0.699 to 0.705) | 0.757 | 3,858 | 0.97% |
| 8 | 0.808 (0.805 to 0.812) | 0.847 | 7,011 | 1.76% |
| 16 | 0.888 (0.886 to 0.890) | 0.914 | 13,117 | 3.29% |
| 32 | 0.942 (0.940 to 0.944) | 0.958 | 24,902 | 6.24% |
| 64 | 0.976 (0.975 to 0.977) | 0.983 | 47,772 | 11.97% |
| 128 | 0.992 (0.992 to 0.993) | 0.994 | 92,185 | 23.10% |
| 632 | 1.000 | 1.000 | 399,632 | 100.16% |
The index has $K = 632$ cells. Recall@1 is the share of queries whose single nearest neighbor is returned. Distance computations are $K$ plus the vectors on the probed lists, averaged over the queries. The quartiles are given for recall@10 only; those of the other columns are as narrow.
Several things can be read from the table.
- One probe finds 44 percent of the true neighbors at 0.36 percent of the cost of a scan. The cost is 1,438 comparisons, not the 1,263 of the equal-lists model, because the lists are unequal. The imbalance factor is 1.29 (1.27 to 1.29), and $632 + 1.29 \times 631 = 1{,}446$ is within a percent of what was measured. The largest list holds 2,216 vectors (the median over the seeds) and the smallest 74. No cell was empty in any of the 30 runs.
- Each doubling of $w$ buys less. The first probe returns 0.436 of the neighbors. The next seven raise the recall by 0.372, to 0.808. The next 56 raise it by 0.168, to 0.976.
- High recall is expensive. A recall@10 of 0.9 needs 19 probes (18 to 19) and 15,259 comparisons, 3.8 percent of a scan. A recall of 0.95 needs 37 probes (36 to 38) and 28,478 comparisons, 7.1 percent. A recall of 0.99 needs about 110 probes (the median over the seeds is 110.5; 107 to 113) and 79,173 comparisons, a fifth of a scan. Going from 0.95 to 0.99 multiplies the cost by 2.8.
- The nearest neighbor is easier to keep than the tenth. Recall@1 is above recall@10 at every $w$: a query's nearest neighbor shares its cell more often than its tenth nearest does.
- The seed matters little. The quartiles of recall@10 are at most 0.009 apart. Different k-means runs give different cells and nearly the same curve.
Fewer or more cells
The cost model said that the best number of cells depends on how many are probed: $K = \sqrt{wN}$. A search that needs many probes should therefore prefer more cells than $\sqrt{N}$. The same experiment was run with a quarter as many cells and with four times as many, again with 30 seeds each.
| $K = 158$ | $K = 632$ | $K = 2{,}528$ | |
|---|---|---|---|
| Recall@10 with one probe | 0.509 | 0.436 | 0.359 |
| Distance computations with one probe | 3,240 | 1,438 | 2,786 |
| Imbalance factor | 1.24 | 1.29 | 1.64 |
| Probes for recall@10 of 0.9 | 9 | 19 | 40 |
| Distance computations for recall 0.8 | 12,828 | 7,011 | 6,251 |
| Distance computations for recall 0.9 | 27,714 | 15,259 | 11,709 |
| Distance computations for recall 0.95 | 46,088 | 28,478 | 21,171 |
| Distance computations for recall 0.99 | 116,835 | 79,173 | 60,102 |
With one probe the three indexes behave as the model predicts: 632 cells are the cheapest, and the other two cost about twice as much. Larger cells also hold more of the neighbors, so the recall of one probe falls as $K$ grows, from 0.509 to 0.359. At equal cost the order is different. To reach a recall of 0.9 the index with 2,528 cells needs 11,709 comparisons, the index with 632 needs 15,259, and the index with 158 needs 27,714. The finer partition wins at every recall from 0.8 up, although 2,528 of its comparisons go to the centroids before a single vector is read. It probes 40 cells of about 158 vectors where the coarse index probes 9 cells of about 2,500, and many small cells chosen around the query fit its neighborhood more closely than a few large ones. Jégou, Douze and Schmid (2011, section V.B) report the same of their compressed variant: for a fixed share of the collection visited, more cells gave higher accuracy.
There is a limit to this. The finest index is also the most unequal. Its imbalance factor is 1.64, its largest list holds 962 vectors (the median over the seeds) where the average is 158, and in every run its smallest list holds a single vector. And its first step alone, 2,528 comparisons, costs more than a whole one-probe search of the index with 632 cells. For a collection of this size, a number of cells between $\sqrt{N}$ and a few times $\sqrt{N}$ is the range in which the choice matters little at moderate recall and the larger value is better at high recall. That is a description of these 399,000 vectors and not a rule.
k-means cells against random leaders
The course's cluster pruning chooses its leaders at random and never moves them. An inverted file index moves them, by k-means, to the means of their cells. The comparison below holds everything else fixed: 632 cells on the same GloVe vectors, the same 30 seeds, the leaders being 632 base vectors drawn at random.
| k-means cells | Random leaders | |
|---|---|---|
| Recall@10 with one probe | 0.436 (0.432 to 0.437) | 0.279 (0.273 to 0.285) |
| Distance computations with one probe | 1,438 | 2,263 |
| Imbalance factor | 1.29 (1.27 to 1.29) | 2.63 (2.38 to 2.74) |
| Largest list (median over seeds) | 2,216 | 9,027 |
| Probes for recall@10 of 0.9 | 19 | 37.5 |
| Distance computations for recall@10 of 0.9 | 15,259 | 45,398 |
| Distance computations for recall@10 of 0.95 | 28,478 | 74,906 |
Random leaders lose on both sides of the trade. A probe finds fewer neighbors, 0.279 against 0.436 for the first, and it costs more, because the lists are far more unequal: the imbalance factor is 2.63, and the largest list holds 9,027 vectors, one in 44 of the whole base. To reach a recall of 0.9 the leaders need three times the distance computations of the k-means cells. The twenty iterations of k-means do two things for the index at once. They lower the quantization error, which puts centroids where the vectors are, and in doing so they even out the cells. This is an observation on these vectors. Nothing in k-means aims at equal cell sizes.
The same comparison can be made on the course's own collection. The cluster hypothesis article ran cluster pruning on Cranfield's 1,400 abstracts as sparse TF-IDF vectors with 37 random leaders, and found that one probe returned 24.5 percent of the ten documents an exhaustive search ranks highest. The unit text embeddings and dense retrieval encodes the same abstracts and the 225 queries as dense vectors of 384 dimensions (the model sentence-transformers/all-MiniLM-L6-v2, pinned there). On those vectors, with 37 cells and 30 seeds:
| Cells probed $w$ | Random leaders: recall@10 | Share of the collection compared | k-means cells: recall@10 | Share of the collection compared |
|---|---|---|---|---|
| 1 | 40.7% (38.9 to 41.9) | 6.2% | 57.3% (55.6 to 58.4) | 5.9% |
| 2 | 57.9% (57.2 to 59.3) | 9.6% | 73.9% (73.1 to 74.4) | 8.9% |
| 4 | 74.7% (73.8 to 76.3) | 16.0% | 86.6% (85.7 to 87.2) | 14.9% |
| 8 | 88.2% (87.4 to 89.0) | 28.7% | 95.0% (94.4 to 95.3) | 26.1% |
The truth here is the ten nearest abstracts of each query by exact search of the same dense vectors, and the share compared counts the 37 centroids and the vectors on the probed lists.
Three things can be said. With leaders chosen at random in the same way, one probe returns 40.7 percent of the dense top ten where it returned 24.5 percent of the sparse top ten, at about the same cost, 6 percent of the collection. The two figures are not measurements of the same thing, since each is judged against the exhaustive ranking of its own vectors, but they do say that a cell of dense vectors holds more of a query's neighborhood than a cell of sparse ones did. Replacing the leaders by k-means centroids raises the figure again, to 57.3 percent. And even so the index earns little at this size: a recall of 95 percent costs a quarter of a scan, and a scan of 1,400 vectors is no burden to begin with. Benchmarking vector indexes measures where the balance tips.
Where the missed neighbors are
Why does one probe find only 44 percent of the neighbors when the cells are, by construction, groups of similar vectors? The cell ranks of the 10,000 true neighbors (ten for each of 1,000 queries, in the index with 632 cells and seed 0) give the answer in numbers.
Of the 10,000 true neighbors, 4,408 are in the cell nearest the query and 1,425 in the second-nearest. The counts fall quickly at first and then slowly: 7,014 are within the first four cells, 8,073 within eight, 8,934 within sixteen, 9,455 within 32 and 9,773 within 64. The remaining 227 are scattered beyond the 64th cell, and 86 of them beyond the 128th.
The queries differ widely. For 127 of the 1,000, all ten neighbors are in the nearest cell, and one probe is exact. For 137, none of the ten is. For 502 the single nearest neighbor is in the nearest cell. The smallest $w$ that returns the exact ten has a median of 13 over the queries, with quartiles 4 and 39, and for the worst query it is 366: more than half of the 632 cells must be read before that query's tenth neighbor turns up.
This is the cluster hypothesis seen from the side of the index. That article measured, on Cranfield, how often two documents relevant to the same query fall in the same k-means cluster, and found the tendency strong but far from a rule: most such pairs were split. Here the pair is a query and one of its true neighbors, which are as similar as two vectors of the collection can be, and they are still separated 56 percent of the time. The reason is geometric and the next section makes it precise. A partition has boundaries, and in 100 dimensions almost every point is close to one.
Can a search know that it is exact?
A search that probed a few cells returns a list. Could it also say "and this list is certainly the true answer"? Sometimes, by the following bound.
Here is the idea in one sentence: the cell of another centroid lies entirely on the far side of the plane halfway between that centroid and the query's nearest centroid, so nothing in that cell can be nearer to the query than the plane is.
Proposition 2 (the bisector bound). Let $\vec c_1$ be the centroid nearest to the query $\vec q$ and $\vec c_j$ any other centroid. Every vector $\vec x$ in cell $j$ satisfies
$$\lvert \vec q - \vec x \rvert \ge b_j, \qquad b_j = \frac{\lvert \vec q - \vec c_j \rvert^2 - \lvert \vec q - \vec c_1 \rvert^2}{2\, \lvert \vec c_j - \vec c_1 \rvert}.$$
Proof. Let $\vec u = (\vec c_j - \vec c_1)/\lvert \vec c_j - \vec c_1 \rvert$, the unit vector pointing from $\vec c_1$ to $\vec c_j$, and define for any point $\vec z$
$$g(\vec z) = \frac{\lvert \vec z - \vec c_1 \rvert^2 - \lvert \vec z - \vec c_j \rvert^2}{2\, \lvert \vec c_j - \vec c_1 \rvert}.$$
Expanding the two squares, the terms $\lvert \vec z \rvert^2$ cancel, and
$$g(\vec z) = \frac{2\, \vec z \cdot (\vec c_j - \vec c_1) + \lvert \vec c_1 \rvert^2 - \lvert \vec c_j \rvert^2}{2\, \lvert \vec c_j - \vec c_1 \rvert} = \vec z \cdot \vec u - \frac{\lvert \vec c_j \rvert^2 - \lvert \vec c_1 \rvert^2}{2\, \lvert \vec c_j - \vec c_1 \rvert}.$$
So $g$ is the coordinate of $\vec z$ along the direction $\vec u$, shifted by a constant: it is zero on the bisecting plane, positive on the side of $\vec c_j$ and negative on the side of $\vec c_1$. For any two points, $g(\vec x) - g(\vec q) = (\vec x - \vec q) \cdot \vec u \le \lvert \vec x - \vec q \rvert$, by the Cauchy-Schwarz inequality and $\lvert \vec u \rvert = 1$. Now $\vec x$ is in cell $j$, so it is at least as near to $\vec c_j$ as to $\vec c_1$, which says $g(\vec x) \ge 0$. And $g(\vec q) = -b_j$ by the definition of $b_j$. Therefore $\lvert \vec x - \vec q \rvert \ge g(\vec x) - g(\vec q) \ge 0 + b_j$.
The number $b_j$ is the distance from the query to the bisecting plane. It is never negative, because $\vec c_1$ is the nearest centroid, and it uses only distances that step 1 of the search has already computed, plus the distances between centroids, which can be computed once when the index is built.
The certificate. Suppose a search has probed a set $P$ of cells that includes the nearest one, and the $k$th best distance it found is $r$. If $r \le b_j$ for every cell $j$ not in $P$, then no unprobed vector is nearer to the query than $r$, and the list returned is a true list of $k$ nearest neighbors.
On the six points the certificate behaves as it should. For the query at 3.4, $b = (2.6^2 - 2.4^2)/(2 \times 5) = (6.76 - 5.76)/10 = 0.1$: the boundary between the cells is at 3.5, a tenth away. The search found a document at distance 1.4, which is more than 0.1, so nothing is certified, and indeed the answer was wrong. For a query at 2.5, $b = (3.5^2 - 1.5^2)/10 = 1$, and the search finds the document at 2 at distance 0.5. Since $0.5 \le 1$, the answer is certified exact with one probe and five comparisons. Worked problem 1 finds every query for which that happens.
On GloVe the certificate almost never holds. For each of the 1,000 queries, in the index with 632 cells and seed 0, the script finds the smallest $w$ at which the search is in fact exact (all ten true neighbors seen), and the smallest $w$ at which the certificate holds.
The answer is in fact exact at a median of 13 probes. The certificate is another matter. For 840 of the 1,000 queries it first holds at $w = 632$, that is, only when every cell has been read and there is nothing left to bound. It holds within 64 probes for 11 queries, and within 316 probes, half the cells, for 22.
Two numbers explain it. The distance from a query to the plane bisecting its nearest and second-nearest centroids has a median of 0.045 over the queries. The distance from a query to its tenth neighbor has a median of 0.850, and to its first neighbor 0.737. For only 6 queries in 1,000 is the nearest neighbor closer than that plane, the one between the query's two nearest centroids. (The nearest face of the query's cell can belong to another centroid and be nearer still, so the count for the nearest boundary of all is at most 6.) A ball around the query large enough to hold its neighbors therefore crosses the boundaries of a great many cells, and the bound cannot rule any of them out. The neighbors are mostly not in those cells, as the recall curve shows, but the bound has no way of knowing that.
So the index is usually right long before it can prove it. This is a statement about the bound of Proposition 2 in a space of 100 dimensions and not about every conceivable bound, but it is the general experience with partition-based search in high dimensions, and it is the reason these indexes are evaluated by measured recall and not by guarantees. The first article of the unit reaches the same point for k-d trees, whose exact search uses a bound of the same kind and for that reason degrades toward a full scan as the dimension grows.
What is proved here, what is cited, what the experiment shows
Proved on this page. Proposition 1: with exact distances inside the probed cells, recall@$k$ is the share of true neighbors lying in those cells, so it never falls as $w$ grows and reaches 1 at $w = K$. The cost model: with equal lists the cost $K + wN/K$ is least at $K = \sqrt{wN}$, where it is $2\sqrt{wN}$. The expected length of the list a size-proportional query reads is $I \cdot N/K$. Proposition 2, the bisector bound, and the certificate built on it.
Cited. That k-means stops, and at a local minimum only, from the k-means article. The inequality $I \ge 1$, from the worked problems of the cluster hypothesis article. The history of the structure and the published measurements, from Sivic and Zisserman (2003), Jégou, Douze and Schmid (2011) and Douze et al. (2026).
Measured. Everything about how much recall a given number of probes buys, for three numbers of cells and for random leaders. The figures are medians over 30 seeds on one set of word vectors, with k-means trained on a sample, and on one small collection of abstracts. They describe those data. Other vectors give other curves: the ANN-Benchmarks study, the subject of the last article of this unit, found one implementation of this index to reach a recall close to 1 on its image-descriptor and word-vector data and no more than 0.7 on a third dataset, over the settings it tested (Aumüller, Bernhardsson, and Faithfull, 2020, read in the arXiv version 1807.05614v2).
Worked problems
These problems are posed on the article's own examples: the six points of the first section, the cost model, the two traced queries, and a small unbalanced index. The script recomputes every number.
Problem 1 (certified queries on the six points). For the index on the documents 0, 1, 2, 4, 5, 9 with cells $A = \{0, 1, 2\}$ and $B = \{4, 5, 9\}$, find all queries between 0 and 3.5 for which one probe is certified exact by Proposition 2, and all for which one probe is in fact exact.
A query $q$ in that range is nearer the centroid of $A$, at 1, than the centroid of $B$, at 6, so the search probes $A$. The bound for cell $B$ is
$$b = \frac{(6 - q)^2 - (q - 1)^2}{2 \times 5} = \frac{36 - 12q - 1 + 2q}{10} = 3.5 - q,$$
the distance from the query to the boundary at 3.5, as it must be on a line. For $q \ge 2$ the nearest document of $A$ is the one at 2, at distance $q - 2$. The certificate asks for $q - 2 \le 3.5 - q$, that is, $q \le 2.75$. For $q < 2$ the nearest document of $A$ is within 0.5 of the query (the documents 0, 1, 2 are one apart), and $3.5 - q > 1.5$, so the certificate holds. So one probe is certified exact for every query from 0 up to 2.75.
One probe is in fact exact for every query up to 3: the nearest document overall is the one at 2 until the query passes the midpoint of 2 and 4. Between 2.75 and 3 the answer is right and cannot be certified. The document at 4 does not threaten those queries, but the bound knows only where the boundary is, not where the documents beyond it are. Between 3 and 3.5 the answer is wrong, as the first section found for 3.4. The script checks all three ranges on a grid of queries spaced 0.01 apart.
Problem 2 (choosing the number of cells). A collection has $N = 399{,}000$ vectors. Under the equal-lists model, find the best number of cells and the cost for $w = 1$, $w = 4$ and $w = 16$ probes. If the index must be built before $w$ is known, what does building for $w = 1$ cost a search that turns out to need $w = 16$?
By the derivation above, $K^* = \sqrt{wN}$ and the cost is $2\sqrt{wN}$. With $\sqrt{N} = 631.7$:
| Probes $w$ | Best $K = \sqrt{wN}$ | Cost $2\sqrt{wN}$ | Share of an exact search |
|---|---|---|---|
| 1 | 632 | 1,263 | 0.32% |
| 4 | 1,263 | 2,527 | 0.63% |
| 16 | 2,527 | 5,053 | 1.27% |
The best $K$ doubles each time $w$ is multiplied by four. An index built with $K = 632$ and searched with $w = 16$ costs $632 + 16 \times 399{,}000/632 = 632 + 10{,}101 = 10{,}733$ comparisons, a little over twice the 5,053 of an index built for 16 probes. The comparison is not as simple as it looks, though: sixteen probes of a 2,527-cell index open sixteen cells of 158 vectors, and sixteen probes of a 632-cell index open sixteen cells of 631, four times as much of the collection. The two searches do not have the same recall. The model says what a search costs and nothing about what it finds, which is why the section on measurement compares indexes at equal cost and not at equal $w$.
Problem 3 (recall from cell ranks). The ten true neighbors of the query "epidemic" have cell ranks 2, 2, 2, 2, 3, 2, 2, 2, 3, 2 in the index with 632 cells. The three nearest cells hold 385, 368 and 560 vectors. Find the recall@10 and the cost for $w = 1$, 2 and 3.
By Proposition 1 a neighbor is returned exactly when $w$ is at least its cell rank. No rank is 1, eight are 2 and two are 3.
| $w$ | Neighbors with cell rank at most $w$ | Recall@10 | Cost |
|---|---|---|---|
| 1 | 0 | 0.0 | $632 + 385 = 1{,}017$ |
| 2 | 8 | 0.8 | $632 + 385 + 368 = 1{,}385$ |
| 3 | 10 | 1.0 | $632 + 385 + 368 + 560 = 1{,}945$ |
The third probe costs the most of the three. The first bought nothing at all: the 385 comparisons in the nearest cell found nothing that belongs in the answer. On average over the queries, later probes buy less than earlier ones, as the table of the measurement section shows. For a single query the order can be anything.
Problem 4 (the imbalance factor). An index over $N = 1{,}000$ vectors has four cells with 700, 100, 100 and 100 vectors. Find the imbalance factor, and the expected number of vectors a one-probe search scans if queries land in cells in proportion to their sizes. Compare with four equal cells.
$$\sum_i n_i^2 = 700^2 + 3 \times 100^2 = 490{,}000 + 30{,}000 = 520{,}000, \qquad I = \frac{K}{N^2} \sum_i n_i^2 = \frac{4 \times 520{,}000}{1{,}000{,}000} = 2.08 .$$
The expected list length is $\sum_i n_i^2 / N = 520$, which is $I \times N/K = 2.08 \times 250$. Directly: a query lands in the large cell with probability 0.7 and scans 700 vectors, or in a small cell with probability 0.3 and scans 100, and $0.7 \times 700 + 0.3 \times 100 = 520$. Four equal cells of 250 would scan 250. The unbalanced index does more than twice the work for the same number of cells. The index of this article is milder: its imbalance factor was 1.29 with k-means cells and 2.63 with random leaders.
What we have learned
An inverted file index partitions the vectors with k-means and compares a query with the vectors of the $w$ cells whose centroids are nearest. Inside those cells it is exact, so its recall is the share of the true neighbors that lie in them, and that share can only be measured. Its cost is $K$ comparisons with centroids plus the lengths of the lists read. With equal lists the cost is least near $K = \sqrt{wN}$, and unequal lists multiply the scanning by the imbalance factor. On 399,000 GloVe vectors with 632 cells, one probe returned 44 percent of the ten true neighbors at 0.36 percent of the cost of a scan, a recall of 0.9 took 19 probes and 3.8 percent of a scan, and a recall of 0.99 took about 110 probes and a fifth of a scan. K-means cells reached a recall of 0.9 with a third of the work that random leaders needed. A bound from the bisecting planes between centroids can certify an answer exact, and in 100 dimensions it almost never does until nearly every cell has been read.
The index still stores every vector in full, 400 bytes each for the GloVe set, and that is what limits it at large scale. Product quantization replaces each vector on a list by a code of a few bytes, from which distances can still be estimated.
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
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 7.1.6. Cambridge University Press. record · 102 pages
- Pennington, J., Socher, R., and Manning, C. D. (2014). GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 1532–1543. record · 5 pages
- Sivic, J., and Zisserman, A. (2003). Video Google: A text retrieval approach to object matching in videos. In Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV), 1470–1477. record