Approximate nearest neighbor search
ANN
Finds vectors close to a query without measuring every stored vector, by walking or probing an index, at the cost of sometimes missing a true neighbor.
In DocSlurpIllustrated explainer
On this page
The problem: a million distances per question
Vector search turns “Are we on track to beat our FY2027 earnings?” into an embedding and looks for the stored chunk vectors closest to it. The exact way to do that is to measure the distance from the query to every stored vector, sort, and keep the top k. That is k-nearest neighbors, and it is always correct.
It is also linear. With a million chunks and 1,024-dimension vectors, each query does a million distance computations of 1,024 multiply-adds each: about a billion operations, plus reading 4 GB of 32-bit floats. That is fine for a batch job and too slow and expensive for every keystroke of every user.
The trade: measure less, accept small misses
Approximate nearest neighbor (ANN) search uses an index that steers the query toward the right region of the space, so it measures only a small fraction of the vectors. The price is that it can miss a true neighbor. You trade a little recall (the share of the true top-k that comes back) for a lot of speed.
The figure shows the trade on 20 points. On the left, exact search measures all 20 and finds the 3 nearest, at distances 34.9, 36.1 and 39.2. On the right, a graph links each point to its two nearest neighbors. The search starts at a far corner and repeatedly hops to whichever linked point is closest to the query:
- Start at the lower-left point, 231.0 away. Its neighbors are measured; the best is 144.3 away. Hop.
- From there, the best neighbor is 91.9 away. Hop.
- Then 39.2. Hop.
- Then 34.9. Hop.
- No neighbor of that point is closer. Stop.
It measured 8 points instead of 20 and returned the closest three it saw: 34.9, 39.2 and 50.5. The true second neighbor, at 36.1, sits just above the query, but its links lead to points the walk never visited. Recall for this query is 2 of 3.
Three families of index
Every ANN index decides which vectors are worth measuring.
- Graphs (such as HNSW) link each vector to its neighbors and walk the links, as in the figure. HNSW adds sparse upper layers for long jumps, and keeps a list of candidates instead of a single current point, so it rarely gets stuck the way the figure’s simple walk does.
- Clusters (such as IVF) group vectors around centroids and search only the few clusters closest to the query. Misses happen when a neighbor sits just across a cluster border.
- Compression (quantization, product quantization) makes each distance cheaper by storing smaller approximate vectors. It is usually combined with a graph or clusters.
Each family has a knob that trades speed for recall: the candidate list size for graphs (often called ef), the number of clusters probed for IVF (nprobe), and how many top candidates are re-scored at full precision (a refine or rerank factor) for compressed vectors. Turning the knob up measures more vectors and misses fewer.
Where it breaks
- Filters fight the index. “Nearest chunks, but only from
travel-desk-guide.pdf” is hard. Filter after the search and the top results may all belong to other documents, leaving nothing. Filter before and the graph or clusters may no longer connect the remaining points well. Engines handle this differently, and recall under tight filters is worth testing directly. - Recall is per query and per corpus. An index tuned to 95% recall on one dataset can do worse on another, especially with clustered data or many near-duplicates. Published benchmark numbers describe their benchmark, not your project.
- Fresh writes may not be indexed yet. Many indexes are rebuilt or extended in batches. Rows written since the last build are typically searched exhaustively, which is exact but slower as the unindexed tail grows.
- Small collections don’t need it. Below a few thousand vectors, exact search is fast enough and has perfect recall. An index adds build time and memory for no benefit.
When to use it
Use ANN when exact search is too slow or too expensive at your size and query rate, and when a missed neighbor is tolerable because something downstream compensates: retrieving more candidates than you show, fusing with keyword search, or reranking a larger shortlist. Measure recall@k against exact search on a sample of real queries before and after changing index settings.
In DocSlurp
Each project’s chunk vectors live in LanceDB. Background maintenance builds an HNSW index with 8-bit scalar quantization once a table reaches 1,000 rows; smaller tables are searched exhaustively. New rows are folded into the index on a cadence (by default every 2,000 rows, 20 commits or five minutes), and rows written in between are scanned exactly. Searches apply the document-scope filter before choosing neighbors, so a narrow scope cannot be crowded out by other documents’ vectors.
In DocSlurp
In DocSlurp
Vector search runs on LanceDB. Once a project table reaches 1,000 rows (vectorIndexMinRows), maintenance builds an HNSW index with scalar quantization (core/worker/src/stages/lancedb-maintenance.ts). Smaller tables, and rows written since the last index refresh, are searched exhaustively.