Vector Search on Disk and with Filters

Three assumptions of an in-memory vector index and what removing each one costs. DiskANN's graph on a solid-state drive, with the pruning rule of its Vamana graph and a proof that on the fully pruned graph it makes a greedy walk toward a stored point converge geometrically; anisotropic vector quantization, the loss behind ScaNN, with its decomposition checked numerically and its codebooks trained on GloVe vectors; a metadata filter combined with a vector search by filtering first, after or during, with the regime in which each fails measured over 30 seeds; and deletes and updates in a graph index. Statements about current systems are confined to named published methods as of November 2026. Worked problems lay out a disk record, prune a neighbor list by hand, choose a codeword under the anisotropic loss and find the selectivity at which a scan beats the graph.

Take the query epidemic and the 5,000 most frequent GloVe words again, and add a condition: only 50 of the 5,000 words are allowed as answers, a random one in a hundred. The nearest allowed words are problem, efforts and possibly, none of them near. The index of the previous article can be asked for its 100 nearest words and the forbidden ones struck out: that costs 922 distance computations and leaves one word, problem. It can instead be made to keep searching until it holds enough allowed words. That finds all ten and costs 4,672 distance computations, nearly a full scan of the 5,000. Comparing the query with the 50 allowed words directly costs 50. When does a filter turn a fast index into a slow one, and what can be done about it? The answer depends on the share of the vectors that pass the filter and on where they lie. Each way of combining a filter with a vector search has a regime in which it fails.

The filter is one of three assumptions that the indexes of this unit have made so far. They assume that the vectors and the index fit in memory, that every stored vector is a legitimate answer to every query, and that the set of vectors does not change. This article removes them one at a time. It is the unit's fast-moving material. Every statement below about a system is a statement about a named method in a paper that we read, reported as that paper's result. The field as a whole is described only as of November 2026.

Here is the route. First the memory assumption: DiskANN, which keeps the graph on a solid-state drive, and the pruning rule that makes its graph suit a disk. Then the other way to save memory, compressing the vectors, with the quantization loss that Guo et al. introduced for dot-product search and released as ScaNN. Then filters: three strategies, the arithmetic of when each fails, and an experiment on GloVe. Finally deletes and updates. The article assumes HNSW, whose search routine everything here modifies, and product quantization. Numbers come from tools/experiments/vectors/vector-search-on-disk-and-with-filters.py and filters_runs.py.

A graph on a solid-state drive

The problem

HNSW needs the vectors in memory, because every step of a search computes distances to them. A billion vectors of 128 bytes each are 128 GB before any link is stored. Subramanya et al. (2019) describe the two established ways around this. One compresses the vectors and searches the compressed form. That fits in memory but, in their account, levels off at a 1-recall@1 of about 0.5 on a billion points, because the compression is lossy. The other splits the set over several machines, each with its own in-memory index, the sharding that search at scale describes for text indexes.

Their system, DiskANN, keeps the graph and the full vectors on a solid-state drive (SSD) and only compressed vectors in memory. The difficulty is the cost of a read. The paper puts a random read of an inexpensive SSD at "a few hundred microseconds", against a target of a few milliseconds for a whole query. A search can therefore afford a few dozen reads, and, more strictly, only a handful of round trips to the drive, since reads issued together return together. In the paper's words the design has to reduce "the number of random SSD accesses to a few dozen" and "the number of round trip requests to disk to under ten, preferably five". A graph search as HNSW performs it reads one neighbor list per step and takes its steps one after another. The whole design follows from making the steps few and wide.

The Vamana graph and its pruning rule

DiskANN builds its own graph, called Vamana, a single layer with a fixed start point (the medoid of the data). Two routines define it. GreedySearch is the layer search of the previous article with a list of length $L$: repeatedly take the nearest unexpanded element of the list, add its out-neighbors, and keep the nearest $L$. RobustPrune chooses at most $R$ out-neighbors for a point $p$ from a candidate set $V$, with a parameter $\alpha \ge 1$:

  1. Take the candidate $p^*$ nearest to $p$ and make it an out-neighbor.
  2. Remove from $V$ every candidate $p'$ with $\alpha \cdot d(p^*, p') \le d(p, p')$.
  3. Repeat until $V$ is empty or $p$ has $R$ out-neighbors.

With $\alpha = 1$ this is the heuristic of HNSW: a candidate is dropped when a chosen neighbor is at least as near to it as $p$ is. With $\alpha > 1$ a candidate is dropped only when a chosen neighbor is nearer to it by the factor $\alpha$, so fewer are dropped and more links, and longer ones, survive. The paper names this as the main difference from HNSW and from the NSG graph of Fu et al. (2019), both of which, it says, "implicitly use $\alpha = 1$". Two further differences are stated there. Vamana prunes over all the points a search visited, where HNSW prunes over the final list only. It also makes two passes over the data, the first with $\alpha = 1$.

Here is what the factor buys, in one sentence: each step of a greedy walk toward a stored point then divides the remaining distance by $\alpha$, so the walk is short. The paper states this without proof for the idealized graph in which every point is pruned against all others, and for a walk whose target is one of the points. That statement can be proved in a few lines.

Proposition 1 (geometric convergence). Let $\alpha > 1$, and let every point $v$ of a finite set $P$ have the out-neighbors RobustPrune$(v, P \setminus \{v\}, \alpha, R)$ with $R = \lvert P \rvert - 1$, so that the degree bound never applies. Let $t$ be a point of $P$. Then from any $v \ne t$ the greedy step, which moves to the out-neighbor of $v$ nearest to $t$, either reaches $t$ or reaches a point $u$ with $d(u, t) \le d(v, t)/\alpha$. A greedy walk from any start $s$ reaches $t$ in at most $\log_\alpha (d(s, t)/d_{\min}) + 1$ steps, where $d_{\min}$ is the smallest distance between two points of $P$.

Proof. The point $t$ is among the candidates of $v$. RobustPrune ends only when the candidate set is empty, so $t$ either became an out-neighbor of $v$ or was removed. If it is an out-neighbor, the greedy step moves to it, since no point is nearer to $t$ than $t$. If it was removed, it was removed in step 2 for some chosen out-neighbor $p^*$ with $\alpha \cdot d(p^*, t) \le d(v, t)$. The greedy step moves to the out-neighbor $u$ nearest to $t$, so $d(u, t) \le d(p^*, t) \le d(v, t)/\alpha$. After $j$ steps that have not reached $t$ the distance is at most $d(s, t)/\alpha^j$, and it is at least $d_{\min}$, so $j \le \log_\alpha(d(s, t)/d_{\min})$. One more step reaches $t$ or contradicts this bound. $\blacksquare$

The proposition is about a target that is stored. For a query that is not one of the points the statement is false as written: the walk cannot end at the query, and what Indyk and Xu (2023, Theorem 3.4) prove for this graph is that it reaches a point within a constant factor of the nearest distance in a number of steps logarithmic in the ratio of the largest to the smallest distance between points.

With $\alpha = 1$ the argument gives only $d(u, t) \le d(v, t)$. If no two points are equally distant from $t$, the inequality is strict, and the walk still reaches $t$. This is proved by the same argument: every $v \ne t$ has an out-neighbor strictly nearer to $t$, so each step strictly decreases the distance to $t$, no point is visited twice, and since $P$ is finite the walk ends; it can end only at a point with no out-neighbor nearer to $t$, which is $t$ itself. But nothing bounds its length by a logarithm: for points on a line, as the DiskANN paper notes, the graph is a chain. Where two distances are equal the walk can stall. The script builds these idealized graphs and checks every walk. On the twelve points of the previous article there are 132 walks between distinct points. With $\alpha = 1$ only 112 of the 132 reach their target, since the coordinates are whole numbers and ties are common. With $\alpha = 1.5$ and $\alpha = 2$ all 132 do, in at most 4 and 3 steps. On 300 random points in 8 dimensions the largest distance is 8.2 times the smallest. Their coordinates are whole numbers too, and ties occur, though rarely: 11 of the 300 points have two other points at the same distance from them, and in all there are 538 pairs of pairs of points at equal distances. So the hypothesis of the statement for $\alpha = 1$ fails when one of those 11 is the target, and for those walks its conclusion is observed, not proved. Proposition 1 needs no such hypothesis. Every walk reached its target for each $\alpha$, all 89,700 between distinct points, so with $\alpha = 1$ the ties never fell at a deciding step. The longest walk takes 10 steps with $\alpha = 1$, 6 with $\alpha = 1.2$ and 3 with $\alpha = 2$, within the proposition's bounds of 12.5 and 4.0 for the last two.

The price is the degree. On the 300 points the mean out-degree is 6.8 with $\alpha = 1$, 16.5 with $\alpha = 1.2$ and 123.7 with $\alpha = 2$; on the twelve points it is 2.33, 4.42 and 5.50. Fewer steps are bought with longer lists. That is the right trade on a drive, where a step costs a round trip and a longer list costs almost nothing extra to read. A real Vamana graph bounds the degree by $R$ and prunes against a search's visited set, not against all points, so the proposition does not apply to it as built. Indyk and Xu (2023) prove a worst-case bound for the unbounded "slow preprocessing" version. They also construct point sets on which the practical version needs to scan a tenth of the data, as the HNSW article reports.

The rest of DiskANN is the arrangement of bytes (sections 3.2 to 3.5 of the paper).

  • On the drive, each point has a fixed-size record: its full-precision vector followed by its at most $R$ neighbor ids, padded to the same length. The record of point $i$ is then found by arithmetic, and no table of offsets is kept in memory.
  • In memory, each point has a short product quantization code (the paper gives 32 bytes as an example). The search computes its distances from these codes, so deciding where to go next needs no read.
  • Beam search. In place of expanding the single nearest unexpanded element, the search reads the records of the $W$ nearest at once (the paper suggests 2, 4 or 8) and merges all their neighbors into the list. One round trip then advances the search by $W$ elements.
  • Caching. The records within a few hops of the start point are kept in memory, since every search passes through them.
  • Re-ranking for free. A record holds the full vector next to the neighbor list, so each read also delivers the exact vector of the element read. The final answer is ranked by exact distances to the elements the search expanded, at no extra reads.

The paper reports that on the billion-point SIFT set this design "serves > 5000 queries a second with < 3ms mean latency and 95%+ 1-recall@1 on a 16 core machine" with 64 GB of memory. The billion-point index was built on that machine in about five days, by indexing overlapping partitions and merging the graphs. Those are the authors' measurements on their hardware.

Round trips, measured on this unit's graph

We have no drive to measure, but the effect of the beam can be counted. The experiment runs DiskANN's search on layer 0 of the HNSW graphs of the previous article (5,000 GloVe vectors, $M = 16$, 30 seeds), entering where the upper layers lead. The list has length $L = 50$, and the queries are every tenth of the unit's 1,000. A round is one batch of up to $W$ records read.

Beam width $W$ Round trips per query Elements read per query Distance computations per query Recall@10
1 54.0 (53.8 to 54.3) 54.0 436 0.870 (0.867 to 0.871)
2 28.7 (28.5 to 28.9) 55.4 447 0.873 (0.869 to 0.875)
4 16.4 (16.2 to 16.5) 58.6 472 0.876 (0.873 to 0.880)
8 10.7 (10.6 to 10.8) 66.5 536 0.886 (0.882 to 0.889)

With $W = 1$ the search is the ordinary one, and it makes 54.0 round trips per query, one for each element it expands. With $W = 8$ it makes 10.7. The beam is not free. The search with $W = 8$ reads 66.5 records where the sequential one reads 54.0, and computes 536 distances in place of 436. It expands several elements before it knows which of them a better candidate would have made unnecessary. Recall rises a little, from 0.870 to 0.886, since more elements are expanded. Assume 0.2 ms per round trip, a figure inside the paper's "few hundred microseconds" and not a measurement. The reads of one query then take 10.8 ms without the beam and 2.1 ms with it. The same count shows why the paper wants a graph with fewer hops to begin with. The graphs used here are HNSW's, pruned with $\alpha = 1$, on 5,000 vectors. The paper's finding that Vamana needs two to three times fewer hops than HNSW on large sets was not tested.

DiskANN keeps compressed vectors in memory to guide its search. Product quantization chooses its codewords to minimize the reconstruction error, the squared distance between a vector and its codeword. Guo et al. (2020) asked whether that is the right thing to minimize when the codes are used to estimate dot products. Their answer is the quantizer of Google's ScaNN library. The paper itself names no library: it links its open-source code, in a repository folder named scann, whose README calls the library ScaNN (Scalable Nearest Neighbors) and cites the paper (as of November 2026). The Faiss authors also describe the paper as the one accompanying the ScaNN library (Douze et al., 2026, section 2 of the arXiv version, 2401.08281v4). This section states their loss, checks it numerically and tries it on the unit's vectors.

Reconstruction error treats all queries alike

Let $\vec x$ be a stored vector, $\tilde x$ its codeword and $\vec r = \vec x - \tilde x$ the residual. For a query $\vec q$ the error of the estimated dot product is $\vec q \cdot \vec x - \vec q \cdot \tilde x = \vec q \cdot \vec r$. If the query is equally likely to point in any direction, the mean squared error is proportional to the reconstruction error:

$$E\big[(\vec q \cdot \vec r)^2\big] = \vec r^{\mathsf T} E\big[\vec q\, \vec q^{\mathsf T}\big] \vec r = \frac{\lvert \vec r \rvert^2}{m} \quad \text{for } \vec q \text{ uniform on the unit sphere in } \mathbb{R}^m,$$

because $E[\vec q\,\vec q^{\mathsf T}]$ is then a multiple of the identity matrix, and its trace is $E[\lvert \vec q \rvert^2] = 1$, so the multiple is $1/m$. This is the argument Guo et al. give for why minimizing reconstruction error has been the standard choice.

Their observation is that the average runs over all queries, while a search cares only about the queries for which $\vec x$ is a candidate for the top of the ranking, those with a large $\vec q \cdot \vec x$. For most queries $\vec x$ is far down the list and an error in its score changes nothing.

The score-aware loss and its decomposition

Guo et al. define the score-aware quantization loss with a weight function $w$ of the true score (their Definition 3.1):

$$\ell(\vec x, \tilde x, w) = E_{\vec q}\big[\, w(\vec q \cdot \vec x)\, (\vec q \cdot \vec r)^2 \,\big].$$

Split the residual into the part along $\vec x$ and the part at right angles to it,

$$\vec r_\parallel = \frac{(\vec r \cdot \vec x)\, \vec x}{\lvert \vec x \rvert^2}, \qquad \vec r_\perp = \vec r - \vec r_\parallel.$$

Their Theorem 3.2 states that for queries uniform on the unit sphere the loss is a weighted sum of the two squared lengths,

$$\ell(\vec x, \tilde x, w) = h_\parallel \lvert \vec r_\parallel \rvert^2 + h_\perp \lvert \vec r_\perp \rvert^2,$$

with weights $h_\parallel$ and $h_\perp$ that depend on $w$, on $\lvert \vec x \rvert$ and on the dimension, given as integrals over the angle between $\vec q$ and $\vec x$. Their Theorem 3.3 states that $h_\parallel \ge h_\perp$ whenever $w$ is zero for negative scores and non-decreasing for positive ones. The loss is called anisotropic because it penalizes the residual differently in different directions: an error along $\vec x$ costs more than an error across it.

The reason can be seen without the integrals. A query with a large dot product with $\vec x$ points mostly along $\vec x$. Its dot product with the residual therefore picks up the parallel part of the residual almost in full and the orthogonal part only through the query's small sideways component.

For the weight that counts only scores above a threshold, $w(t) = 1$ for $t \ge T$ and 0 otherwise, the paper writes $\eta = h_\parallel / h_\perp$ and gives its limit in high dimension (Theorem 3.4): $\eta/(m - 1)$ tends to $(T/\lvert \vec x \rvert)^2 / (1 - (T/\lvert \vec x \rvert)^2)$. For unit vectors, $m = 100$ and $T = 0.2$ the limit formula gives $\eta = 99 \times 0.04/0.96 = 4.125$, the value the paper quotes for its GloVe experiments.

We did not reproduce the proofs. The script checks the statements numerically for unit $\vec x$ and $T = 0.2$. It evaluates the paper's integrals for $h_\parallel$ and $h_\perp$ and compares their ratio with a simulation of four million uniform queries. In 3 dimensions the integrals give $\eta = 1.409$ and the simulated ratio of the loss for a purely parallel residual to that for a purely orthogonal one is 1.407. In 100 dimensions the integrals give $\eta = 5.953$ and the simulation 6.030. A residual with both parts has the loss the weighted sum predicts, with no cross term, to within the simulation's noise. One detail is worth knowing. The paper describes the ratio as quickly approaching the limit (the caption of its Fig. 2) and proposes the limit as a proxy that is easy to evaluate. By our integration the exact ratio at $m = 100$ is still 5.953, 44% above the limit value 4.125. The experiment below uses 4.125, as the paper does.

Example (the nearer codeword is the worse one). Let $\vec x = (1, 0)$ and take two codewords, $a = (0.8, 0)$ and $b = (1, 0.3)$. The residual of $a$ has squared length 0.04, all of it parallel; that of $b$ has squared length 0.09, all of it orthogonal. Reconstruction error prefers $a$. With $\eta = 4.125$ the anisotropic loss is $4.125 \times 0.04 = 0.165$ for $a$ and 0.09 for $b$, and prefers $b$. For a query at 10 degrees from $\vec x$ the true dot product is 0.985; codeword $a$ gives 0.788, an error of +0.197, and codeword $b$ gives 1.037, an error of -0.052. For a query at right angles to $\vec x$ the true value is 0, $a$ gives 0 and $b$ gives 0.3: the anisotropic choice is worse exactly where the score is low and the error does not matter.

Codebooks under the loss

For a single codebook the paper's procedure (its section 4) is Lloyd's algorithm of k-means with both steps changed. Each vector is assigned to the codeword that minimizes its anisotropic loss, not to the nearest. Each codeword is then set to the minimizer of the summed loss of its vectors, which Theorem 4.2 gives in closed form; for unit vectors with weights $\eta$ and 1 it is

$$\tilde c = \Big( n I + (\eta - 1) \sum_i \vec x_i\, \vec x_i^{\mathsf T} \Big)^{-1} \eta \sum_i \vec x_i,$$

the sums running over the $n$ vectors assigned to the codeword. With $\eta = 1$ this is their mean, the k-means update. The paper notes that neither step can increase the loss, so the iteration converges, and extends the procedure to product quantization, which this article does not implement.

On the unit's vectors

The experiment quantizes the 5,000 unit vectors with one codebook of 256 codewords, eight bits per vector. It first runs k-means (25 iterations from random data points), then ten anisotropic iterations with $\eta = 4.125$ started from the k-means codebook, for 30 seeds of the initial codewords. The script asserts that the anisotropic loss never increased from one step to the next in any run.

Codebook Parallel residual, mean square Orthogonal residual, mean square Mean length of a vector's codeword
k-means 0.1653 0.2294 0.776
Anisotropic, $\eta = 4.125$ 0.0263 0.4778 1.104

The anisotropic codebook does what it is built to do. The mean squared parallel residual falls from 0.1653 to 0.0263, to less than a sixth. The orthogonal residual doubles, from 0.2294 to 0.4778, so the reconstruction error grows from about 0.39 to about 0.50. The codewords also change length. A k-means codeword is the mean of unit vectors and is shorter than they are: the codeword of a vector has length 0.776 on average over the 5,000 vectors, so it underestimates the dot product of every query that points along its vectors. Under the anisotropic codebook the same average is 1.104. The anisotropic loss per vector, $\eta \lvert \vec r_\parallel \rvert^2 + \lvert \vec r_\perp \rvert^2$, is 0.9111 for the k-means codebook as trained and 0.9073 once its vectors are reassigned under the anisotropic loss, the starting point of the iterations. After them it is 0.5863.

Whether that helps a search is a separate question, and the answer depends on the queries.

The next table gives the mean squared error of the quantized dot product over three sets of pairs, and a recall.

Codebook Uniform queries, dot product at least 0.2 GloVe queries, dot product at least 0.2 GloVe queries, true ten nearest True ten among the 100 best quantized scores
k-means 0.01157 0.00969 0.03398 0.626 (0.615 to 0.633)
Anisotropic, $\eta = 4.125$ 0.00604 0.01351 0.03809 0.633 (0.627 to 0.645)

The first column uses 2,000 queries drawn uniformly on the unit sphere for each seed, the distribution the theory assumes, and the pairs whose true dot product is at least 0.2. There the anisotropic codebook halves the error, from 0.01157 to 0.00604, and it is the better codebook in 30 of the 30 seeds. The loss delivers what Theorem 3.2 says it should.

The other columns use the unit's GloVe queries. On their pairs with a dot product of at least 0.2 the anisotropic codebook is worse, 0.01351 against 0.00969. On each query's true ten nearest vectors it is worse again, 0.03809 against 0.03398, and it is the better codebook in 0 of the 30 seeds. The recall in the last column is the share of the true ten that are among the 100 highest quantized scores. It is almost unchanged: 0.633 against 0.626, higher for the anisotropic codebook in 25 of the 30 seeds.

A reading consistent with these numbers is that real queries are not uniformly distributed around a vector. The derivation needs the part of the query at right angles to $\vec x$ to point in a random direction, so that it meets the enlarged orthogonal residual only by chance. Words near a given word differ from it in the directions in which the data vary, and those are the directions in which a cluster's vectors differ from their codeword. The experiment does not test this explanation. It also differs from the paper's setting in ways that matter. It uses one codebook at eight bits per vector on 5,000 vectors. It also retrains the codebook under the new loss. Guo et al. use product quantization on 1.2 million GloVe vectors. In their Fig. 3a, at 200 bits per vector, they keep a codebook trained under reconstruction loss and change only how the vectors are assigned to codewords. There they report that the loss raises the recall of the true nearest neighbor among ten candidates from about 0.83 to about 0.90 (as read from the plot). The fair summary has three parts. The loss is derived for uniformly distributed queries. It performs as derived on such queries. Its benefit on real queries is an empirical matter, which this small experiment did not reproduce.

Filters

The problem and three strategies

Stored vectors usually carry other data: a date, a language, an owner, a price. A filtered query asks for the $k$ nearest vectors among those whose data satisfy a condition. Write $s$ for the selectivity of the filter, the share of the $N$ vectors that pass it (the definition of Patel et al., 2024; Gollapudi et al., 2023, call the same quantity specificity). Recall is measured against the true $k$ nearest among the passing vectors.

There are three places to apply the filter.

  • Filter first (pre-filtering): find the passing vectors by other means, such as an inverted index on the attribute, and compare the query with each of them. The answer is exact and the cost is $sN$ distance computations.
  • Filter after (post-filtering): search the vector index for the $k'$ nearest of all the vectors, with $k' > k$, and discard those that fail.
  • Filter during: apply the filter inside the index's search, so that failing vectors do not occupy places in the result.

Where each fails: the arithmetic

Filter first fails by cost when many vectors pass. Its cost $sN$ grows with the collection, and at $s = 0.5$ it is half a full scan. It has no failure of recall.

Filter after fails by recall when few vectors pass. If the passing vectors are spread evenly among the query's neighbors, a list of $k'$ nearest holds about $s k'$ passing ones. To expect $k$ of them takes $k' = k/s$: 100 for $k = 10$ at $s = 0.1$, and 1,000 at $s = 0.01$. A fixed $k'$ therefore fails below $s = k/k'$. A $k'$ that grows as $k/s$ makes the index search for a number of neighbors that approaches $N$, at which point a graph index costs more than a scan. Patel et al. (2024, section 3.2) give the same accounting and add the case that makes it worse. Suppose the passing vectors are far from the query, clustered somewhere else. Then the query's nearest $k'$ contain almost none of them, whatever the filter's overall selectivity, and the cost can reach the order of $N$. They call the tendency of passing vectors to lie near or far from the query the query correlation of the workload.

Filter during has two forms with opposite failures. In form (a) the search traverses every element as usual but admits only passing elements to its result list. This is correct in the same sense as the unfiltered search, and it adapts to the filter by itself. But it does the work of the post-filter: to collect a list of ef passing elements it must explore a region holding about ef$/s$ elements. In form (b) the search follows only links that lead to passing elements, so it never computes a distance to a failing one. Its failure is connectivity. An element with $D$ links has about $sD$ links to passing elements, and when $sD$ falls toward 1 the passing elements no longer form a connected graph. The graphs of the previous article have about 13 links per element in layer 0, so the estimate predicts trouble below $s \approx 0.1$.

The two published methods described after the experiment filter inside a graph and change the graph so that form (b) stays connected.

The experiment

The base is again the 5,000 most frequent words. The index is the HNSW graph of the previous article ($M = 16$, efConstruction = 100), built with seeds 0 to 29. The queries are every tenth of the unit's 1,000, with $k = 10$. Two kinds of filter are drawn for each seed at six selectivities.

  • A random filter passes a uniformly drawn subset of $sN$ vectors.
  • A clustered filter passes the $sN$ vectors nearest to an anchor vector drawn at random. The passing vectors then lie together, far from most queries.

Six strategies are compared. Filter first scans the passing vectors. After, list 100 searches with efSearch = 100 and keeps the first ten passing results. After, list $2k/s$ does the same with efSearch = $20/s$, which is 40, 100, 200, 400, 1,000 and 2,000 for the six selectivities. During (a) and During (b) are the two forms above with a list of 20 passing elements. During (c) is form (b) with the neighbor lookup that Patel et al. describe for their ACORN-1 variant, applied to this unit's graph. The neighbors of an element are taken to be its passing neighbors and the passing neighbors of its neighbors, nearest lists first, cut to $M = 16$. Strategy (c) borrows only that lookup rule; ACORN builds its own index, which was not reproduced. A filter check is counted as free, and the cost is distance computations per query. The tables give medians over the 30 seeds, with quartiles for recall.

Random filter, recall@10:

$s$ Passing Filter first After, list 100 After, list $2k/s$ During (a) During (b) During (c)
0.5 2,500 1.000 0.913 (0.907 to 0.922) 0.794 (0.784 to 0.801) 0.791 (0.786 to 0.802) 0.541 (0.514 to 0.562) 0.658 (0.647 to 0.665)
0.2 1,000 1.000 0.872 (0.859 to 0.883) 0.872 (0.859 to 0.883) 0.872 (0.864 to 0.883) 0.242 (0.219 to 0.274) 0.731 (0.721 to 0.744)
0.1 500 1.000 0.787 (0.777 to 0.799) 0.916 (0.903 to 0.929) 0.923 (0.903 to 0.931) 0.074 (0.053 to 0.087) 0.767 (0.754 to 0.781)
0.05 250 1.000 0.510 (0.484 to 0.522) 0.956 (0.947 to 0.965) 0.954 (0.948 to 0.966) 0.023 (0.018 to 0.031) 0.717 (0.692 to 0.739)
0.02 100 1.000 0.202 (0.180 to 0.219) 0.987 (0.985 to 0.991) 0.989 (0.984 to 0.992) 0.012 (0.009 to 0.017) 0.525 (0.473 to 0.577)
0.01 50 1.000 0.102 (0.085 to 0.111) 0.999 (0.998 to 1.000) 0.999 (0.996 to 1.000) 0.007 (0.005 to 0.012) 0.310 (0.212 to 0.381)

Random filter, distance computations per query:

$s$ Filter first After, list 100 After, list $2k/s$ During (a) During (b) During (c)
0.5 2,500 719 371 367 148 266
0.2 1,000 719 719 707 76 236
0.1 500 719 1,225 1,199 38 190
0.05 250 719 2,043 1,996 28 128
0.02 100 719 3,573 3,514 27 67
0.01 50 719 4,611 4,527 26 41

Clustered filter, recall@10:

$s$ Passing Filter first After, list 100 After, list $2k/s$ During (a) During (b) During (c)
0.5 2,500 1.000 0.837 (0.770 to 0.883) 0.593 (0.531 to 0.683) 0.851 (0.840 to 0.861) 0.621 (0.550 to 0.663) 0.626 (0.582 to 0.645)
0.2 1,000 1.000 0.455 (0.396 to 0.614) 0.455 (0.396 to 0.614) 0.916 (0.898 to 0.933) 0.401 (0.319 to 0.469) 0.690 (0.613 to 0.708)
0.1 500 1.000 0.263 (0.194 to 0.460) 0.464 (0.358 to 0.650) 0.961 (0.942 to 0.973) 0.261 (0.181 to 0.345) 0.721 (0.665 to 0.779)
0.05 250 1.000 0.145 (0.090 to 0.315) 0.530 (0.356 to 0.724) 0.984 (0.974 to 0.991) 0.153 (0.108 to 0.189) 0.738 (0.693 to 0.793)
0.02 100 1.000 0.075 (0.037 to 0.136) 0.706 (0.508 to 0.804) 0.997 (0.994 to 0.999) 0.071 (0.051 to 0.103) 0.639 (0.496 to 0.709)
0.01 50 1.000 0.045 (0.017 to 0.070) 0.831 (0.681 to 0.928) 1.000 (1.000 to 1.000) 0.044 (0.033 to 0.062) 0.448 (0.367 to 0.567)

Clustered filter, distance computations per query:

$s$ Filter first After, list 100 After, list $2k/s$ During (a) During (b) During (c)
0.5 2,500 719 371 670 185 273
0.2 1,000 719 719 1,665 105 244
0.1 500 719 1,225 2,478 66 198
0.05 250 719 2,043 3,226 42 147
0.02 100 719 3,573 4,099 31 82
0.01 50 719 4,611 4,635 28 48
Recall@10 (top) and distance computations per query (bottom) for six ways of combining a filter with a search of 5,000 GloVe vectors, medians over 30 seeds. Read each panel from right (half the vectors pass) to left (one in a hundred passes). Notice that the scan's cost falls with the selectivity while the cost of every graph strategy that keeps its recall rises, so the lines cross. Strategy (c) is ACORN-1's lookup rule on this unit's pruned HNSW graph, not ACORN's index.
Recall@10 (top) and distance computations per query (bottom) for six ways of combining a filter with a search of 5,000 GloVe vectors, medians over 30 seeds. Read each panel from right (half the vectors pass) to left (one in a hundred passes). Notice that the scan's cost falls with the selectivity while the cost of every graph strategy that keeps its recall rises, so the lines cross. Strategy (c) is ACORN-1's lookup rule on this unit's pruned HNSW graph, not ACORN's index.

Each strategy fails where the arithmetic said it would.

  • Filter first is exact everywhere, and its cost is the number of passing vectors. It is the dearest strategy when half the vectors pass and the cheapest that keeps its recall once fewer than about 15% do (the crossing is worked out in Problem 4).
  • After, with a list of 100, loses recall as the filter tightens: 0.913 when half the vectors pass, 0.510 at $s = 0.05$, 0.102 at $s = 0.01$. At $s = 0.01$ a list of 100 holds one passing vector on average, a tenth of the ten wanted, and 0.102 is what was measured. At $s = 0.05$ the search returned fewer than ten results for 97 of the 100 queries (the median over seeds).
  • After, with a list of $2k/s$, keeps its recall under the random filter and pays for it. At $s = 0.01$ it computes 4,611 distances, 92% of a full scan and 92 times the cost of scanning the 50 passing vectors. Under the clustered filter it loses recall as well, 0.455 at $s = 0.2$, because the passing vectors are not among the query's neighbors at all.
  • During (a) behaves under the random filter almost exactly as the long post-filter does, in recall and in cost: collecting 20 passing elements is the same work as collecting $20/s$ elements. Under the clustered filter it is the only graph strategy that keeps its recall (0.851 to 1.000), because it searches until it has found passing elements wherever they are. Its cost climbs to 4,635 distance computations, again nearly a scan.
  • During (b) is cheap because it gives up. Under the random filter its recall is 0.541 at $s = 0.5$, 0.242 at $s = 0.2$ and 0.074 at $s = 0.1$, the selectivity at which an element has about one passing link. Under the clustered filter it does somewhat better at small $s$, since passing vectors are then each other's neighbors, but most queries enter the graph far from them.
  • During (c), the two-hop lookup, restores much of the connectivity. Its recall is 0.658 to 0.767 for $s$ from 0.5 to 0.05, at 128 to 266 distance computations, a fraction of the cost of form (a). It decays below that, to 0.310 at $s = 0.01$. This is a borrowed rule on a graph not built for it, and its numbers say nothing about ACORN itself.

For the random filter the scan and form (a) cross between $s = 0.2$, where the graph costs 707 distance computations against the scan's 1,000, and $s = 0.1$, where it costs 1,199 against 500. The quartiles of the clustered filter are wide because the anchor, and with it the position of the passing vectors, changes with the seed.

Example (the opening query). For epidemic under the random filter of seed 0 at $s = 0.01$, the true answer among the 50 passing words begins problem, efforts, possibly. Filter first costs 50 distance computations. The post-filter with a list of 100 costs 922 distance computations and returns one word. During (a) returns the exact ten after 4,672 distance computations. During (b) returns nothing: the element at which the search enters layer 0 has no passing neighbor. During (c), ACORN-1's lookup on this unit's graph, returns ten words, seven of them correct, for 73 distance computations.

Example (a common misreading). "A filter makes the search cheaper, because fewer vectors qualify." It makes a scan cheaper. For an index it removes the property the index relies on, that the nearest vectors are reachable through a few links. The index pays for every failing vector that stands between the query and the passing ones.

Graphs built for filters

As of November 2026 this section describes two published designs that change the graph itself for filtered search, the ones read for it, and makes no claim about any others.

Filtered-DiskANN (Gollapudi et al., 2023) assumes that each vector carries a set of labels from a finite set and that a query names one label. Its FilteredVamana graph is built with the labels in view. The search for a label starts from a start point chosen for that label and follows only out-neighbors that carry it (their Algorithm 1, the form (b) above). The pruning rule is changed so that the filtered search stays connected. A chosen neighbor $p^*$ may cause a candidate $p'$ to be dropped only if $p^*$ carries every label that $p'$ shares with the point being pruned (their Algorithm 3). A link is thus removed only when the detour through $p^*$ is available to every filtered search that could have used the link. A second variant, StitchedVamana, builds one graph per label and overlays them. The authors report that their algorithms can be tuned to a recall close to 100% for filters with a selectivity as low as $10^{-4}$ to $10^{-6}$, where the other algorithms they tested saturate at a lower recall. They also report outperforming those baselines by an order of magnitude or more. The design's limit is its assumption: the labels must be known when the index is built, and the paper's experiments use queries with one label.

ACORN (Patel et al., 2024) makes no assumption about the conditions, which may be ranges or text matches unknown in advance. It modifies HNSW in the opposite direction from pruning. Each element collects $M \cdot \gamma$ candidate neighbors in place of $M$, so that for a filter of selectivity $s$ an element still has about $\gamma M s$ passing neighbors, which exceeds $M$ when $s > 1/\gamma$. The search follows passing neighbors only, up to $M$ of them. The paper sets $\gamma$ from the smallest selectivity the index is meant to serve and falls back to filtering first for queries estimated to be more selective than that. A compression rule keeps the lists from growing by the full factor. The ACORN-1 variant builds HNSW without its pruning step and widens the lookup to two hops at search time. Strategy (c) applied that lookup to this unit's graph, which is pruned by the heuristic and which ACORN-1 does not use. The pruned graph has fewer links to near elements for a two-hop lookup to find, which may put the rule at a disadvantage here; that was not tested. The authors report 2 to 1,000 times the throughput of the methods they compare with at a recall of 0.9, on their datasets.

ACORN arrives at the cost-based choice that the experiment shows from the other side: below some selectivity the scan wins, and a system needs an estimate of the selectivity to decide. Filtered-DiskANN describes such a plan in an earlier system, AnalyticDB-V, which switches between post-filtering, filtering inside an inverted file and a scan according to the selectivity. Its own answer is different: build the labels into the graph.

Deletes and updates

HNSW grows by insertion, so adding vectors needs nothing new. Removing one is the difficulty. Malkov and Yashunin (2020) leave it open: their discussion (section 6 of the arXiv version, 1603.09320v4) lists "support for element updates and removal" among the things to add.

Singh et al. (2021), in an arXiv preprint for which no peer-reviewed version could be found as of November 2026, examined why removal is hard. They took HNSW, NSG and Vamana graphs over a million vectors and repeatedly deleted 5% of the points and inserted them again. They tried two natural policies. One removes a deleted point's links and does nothing else. The other also links each of its in-neighbors to each of its out-neighbors and prunes. Their Fig. 1 shows the first policy on HNSW and Vamana and the second on NSG; other combinations, they write, behave alike. In each panel the recall at a fixed list size falls steadily over twenty cycles, from about 95% to between 87% and 92% as read from the plot. Yet the index holds the same points after every cycle. They observe that the graph becomes sparser as it is updated, and they suspect that the cause is the aggressive pruning of algorithms such as HNSW and NSG, which favors very sparse graphs.

Their method, FreshDiskANN, has three parts.

  • Lazy deletion. A deleted point is put on a list and left in the graph. Searches use it for navigation and leave it out of the results. This is form (a) of the previous section with the deleted points as the failing ones. Its cost is the one measured there: with half the vectors marked deleted (the random filter at $s = 0.5$), a search with a list of 20 computed 367 distances per query and found 0.791 of the true surviving neighbors. The cost rises as $1/s$ as more are deleted, so deleted points are not free while they remain.
  • Consolidation. When the deleted points reach between 1 and 10 percent of the index, the range the paper suggests, a batch pass removes them. Every point with an out-link to a deleted point takes that point's out-neighbors as candidates and is pruned again with RobustPrune and $\alpha > 1$ (their Algorithm 4). The authors report that with the denser graphs of $\alpha > 1$ the recall stays stable over many cycles.
  • Two indexes. New points go into a small in-memory graph, while the large index on the drive is read-only. A background merge periodically applies the accumulated deletions and insertions to the on-drive index. The arrangement is the one text indexes use, a small mutable segment merged into large immutable ones, which updating an index treats in full.

The paper reports a system that maintains an index of the order of a billion points on one machine, with thousands of inserts, deletes and searches per second each, while keeping a 5-recall@5 above 95%. Its steady-state experiment holds about 800 million points. An update to a vector is a delete followed by an insert.

What is proved here, what is cited, what the experiments show

Proved on this page. The geometric convergence of a greedy walk toward a stored point on a graph pruned with $\alpha > 1$ against all points (Proposition 1). It says nothing about a query outside the set, or about a graph with a degree bound. The identity that makes reconstruction error the mean squared dot-product error for uniform queries. The arithmetic of the filter strategies' costs.

Cited, not proved. The design and the measurements of DiskANN, Filtered-DiskANN, ACORN and FreshDiskANN, each as its paper reports them. Theorems 3.2 to 3.4 and 4.2 of Guo et al. (2020) on the anisotropic loss, which the script checks numerically but does not prove. The worst-case results of Indyk and Xu (2023).

Shown by the experiments, on 5,000 GloVe vectors, 100 queries and 30 seeds. The round trips saved by a beam; the residuals and dot-product errors of a k-means and an anisotropic codebook of 256 codewords; the recall and cost of six filter strategies under random and clustered filters. No drive was used and no system named here was run. The experiments use this unit's own HNSW graph, which none of the cited systems is.

Worked problems

The unit has no course assignments. The problems apply the section's arithmetic to the unit's GloVe set and to the twelve points of the previous article; the script recomputes every number.

Problem 1. Lay out a DiskANN record for the unit's 399,000 vectors with degree bound $R = 32$. How large is the file, how many records fit in a 4,096-byte sector, and what stays in memory with 25-byte codes?

Let a record hold the vector, 100 four-byte numbers, a four-byte count and 32 four-byte neighbor ids. The count is this problem's choice; the paper's layout pads the list with zeros instead. That is $400 + 4 + 128 = 532$ bytes. Seven whole records fit in a sector, since $7 \times 532 = 3{,}724$ and an eighth would not fit. The file is $399{,}000 \times 532$ bytes, 212.3 MB. In memory the codes take $399{,}000 \times 25$ bytes, 9.98 MB, against 159.6 MB for the full vectors. At this size the set fits in memory many times over and a drive would only slow it down. The layout pays when the vectors exceed memory, and the arithmetic is the same.

Problem 2. Choose out-neighbors for element 1 of the twelve points, the point (14, 15), from all the other elements, with RobustPrune and no degree bound, once with $\alpha = 1$ and once with $\alpha = 2$.

Distances below are squared, so the test $\alpha\, d(p^*, p') \le d(p, p')$ becomes $\alpha^2 d^2(p^*, p') \le d^2(p, p')$. With $\alpha = 1$: the nearest candidate is element 6, at 5, and it removes elements 3, 8 and 9, each at least as near to element 6 as to element 1. The nearest remaining is element 10, at 82, which removes elements 0, 2, 4 and 11. Then element 7, at 101, removes element 5. The result is out-neighbors 6, 10, 7. With $\alpha = 2$ a candidate is removed only if a chosen neighbor is at most half as far from it as element 1 is, a factor of 4 in squared distance. Element 6 now removes nothing: element 9, for instance, is at 2 from element 6 and at 5 from element 1, and $4 \times 2 > 5$. Elements 9, 8 and 3 are chosen in turn; element 10 removes 0, 2 and 4; element 7 removes 5; element 11 remains and is chosen. The result is out-neighbors 6, 9, 8, 3, 10, 7, 11. The larger factor more than doubled the list, and by Proposition 1 it guarantees that a greedy step from element 1 toward any other element at least halves the distance.

Problem 3. A unit vector in 100 dimensions has two candidate codewords. The first leaves a residual of squared length 0.30, of which 0.12 is parallel. The second leaves 0.34, of which 0.03 is parallel. Which does reconstruction error choose, and which does the anisotropic loss with $\eta = 4.125$?

Reconstruction error chooses the first, 0.30 against 0.34. The anisotropic loss of the first is $4.125 \times 0.12 + 0.18 = 0.675$, and of the second $4.125 \times 0.03 + 0.31 = 0.434$, so it chooses the second. The second codeword is farther from the vector and estimates the dot products of well-aligned queries better, in expectation over uniformly distributed queries. Whether the same holds for real queries is what the experiment above tested.

Problem 4. Under the random filter, form (a) cost 1,199 distance computations per query at $s = 0.1$. Model its cost as $c/s$ and the scan's as $sN$. Find $c$, the selectivity at which the two cost the same for $N = 5{,}000$, and the same for $N = 399{,}000$ if $c$ did not change.

The median behind the table's 1,199 is 1,198.51, so $c = 119.851$, about 120. The costs are equal when $sN = c/s$, that is, at $s^* = \sqrt{c/N}$. For $N = 5{,}000$ that is $\sqrt{119.851/5{,}000} = 0.155$, or 774 passing vectors, which agrees with the table: the graph is cheaper at $s = 0.2$ and the scan at $s = 0.1$. For $N = 399{,}000$ the same $c$ gives $s^* = 0.0173$, or 6,915 passing vectors. Two cautions apply. The constant $c$ is the cost of an unfiltered search and grows slowly with $N$, which raises $s^*$ somewhat. And the model $c/s$ overstates the graph's cost at small $s$, where the search runs out of vectors: at $s = 0.01$ it predicts 11,985 and 4,527 were measured. The shape of the result survives both. The break-even selectivity falls like $1/\sqrt{N}$, so a larger collection leaves the graph ahead for more filters. The break-even number of passing vectors, $\sqrt{cN}$, grows.

What we have learned

A graph index can live on a drive if its walks are short and wide. DiskANN prunes with a factor $\alpha > 1$. On the idealized graph that provably makes a greedy walk toward a stored point converge geometrically, and it lengthens the lists. It also reads several records per round trip. Compressed vectors in memory guide the walk. For dot-product search the anisotropic loss trades reconstruction error for accuracy on the queries that align with a vector. That trade held for uniform queries and not for this unit's queries at eight bits per vector. A filter can be applied before, after or during the search. Filtering first is exact and costs $sN$. Filtering after or during on an unmodified graph costs about $1/s$ times a search or loses the results. Following only passing links needs a graph built for it. Deleting from a graph is done lazily and repaired in batches.

Every index in this unit has now been described and measured on its own. Benchmarking vector indexes puts them on one set of axes, recall against cost, build time and memory, and asks below what size none of them should be built at all.

References

  • 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
  • Fu, C., Xiang, C., Wang, C., and Cai, D. (2019). Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5), 461–474. record
  • Gollapudi, S., Karia, N., Sivashankar, V., Krishnaswamy, R., Begwani, N., Raz, S., Lin, Y., Zhang, Y., Mahapatro, N., Srinivasan, P., Singh, A., and Simhadri, H. V. (2023). Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the ACM Web Conference 2023 (WWW '23), 3406–3416. record
  • Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., and Kumar, S. (2020). Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), PMLR 119, 3887–3896. arXiv:1908.10396. record
  • Indyk, P., and Xu, H. (2023). Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), 66239–66256. arXiv:2310.19126. record · 2 pages
  • Malkov, Y. A., and Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824–836. arXiv:1603.09320. record · 2 pages
  • Patel, L., Kraft, P., Guestrin, C., and Zaharia, M. (2024). ACORN: Performant and predicate-agnostic search over vector embeddings and structured data. Proceedings of the ACM on Management of Data, 2(3), 1–27. arXiv:2403.04871. record · 2 pages
  • Singh, A., Subramanya, S. J., Krishnaswamy, R., and Simhadri, H. V. (2021). FreshDiskANN: A fast and accurate graph-based ANN index for streaming similarity search. arXiv:2105.09613. record
  • Subramanya, S. J., Devvrit, Kadekodi, R., Krishnaswamy, R., and Simhadri, H. V. (2019). DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019). record · 2 pages