All chapters
  1. Start hereRetrieval is a query. The model reads only what it returns
  2. Foundations · 1What retrieval means: lookup, keyword search, semantic search
  3. Foundations · 2Traditional SQL first: WHERE, indexes, full-text search and BM25
  4. Foundations · 3Vectors without AI: coordinates, distance and nearest neighbors
  5. Foundations · 4Embeddings: how a model turns text into a vector
  6. Foundations · 5Choosing an embedding model: quality, cost, privacy and fit
  7. Search · 6Schema and storage: where the vectors live
  8. Search · 7Exact vector search: compare the query with every row
  9. Search · 8Approximate nearest neighbors: HNSW, IVF and the recall trade
  10. Search · 9PostgreSQL and pgvector: vectors inside a relational database
  11. Search · 10SQLite vector search: one file on one machine
  12. Pipeline · 11Chunking and ingestion: from a document to retrievable units
  13. Pipeline · 12Retrieval pipelines: from a question to the context the model reads
  14. Pipeline · 13Hybrid search: words and vectors together
  15. Pipeline · 14Reranking: a second, more careful look at the candidates
  16. Pipeline · 15Top-k and scale: ten thousand, a hundred thousand, a million rows
  17. Pipeline · 16Two corpora: similar applicants and underwriter precedents
  18. Pipeline · 17Grounded generation: citations, abstention and conflicts
  19. Pipeline · 18Evaluating retrieval: recall@k, MRR, nDCG and faithfulness
  20. Practice · 19Google Cloud choices: Cloud SQL, AlloyDB, Vector Search, Agent Retrieval, RAG Engine, Agent Search
  21. Practice · 20Other ecosystems: libraries, engines and managed services
  22. Practice · 21Operations: migrations, deletes, permissions and freshness
  23. Practice · 22Advanced retrieval: rewriting, hierarchies, late interaction, graphs, agents
  24. Practice · 23Reference architectures: local-first, dual-corpus, managed, Postgres-native
  25. Practice · 24Framework recipes and the decision guide
  26. ReferenceGlossary
  27. AboutAbout this site and its sources
Search · 8

Approximate nearest neighbors: HNSW, IVF and the recall trade

An index that skips most rows answers faster and sometimes misses a true neighbor. HNSW graphs, IVF lists, their build and search parameters, and how to measure what an index loses.

Skip most rows
An ANN index answers a nearest-neighbor query after comparing a small share of the rows. The price: it may miss some true neighbors.
A graph or buckets
HNSW walks a layered graph (M, ef_construction, ef_search). IVF scans the nearest few buckets (lists, nprobe).
Measure what it misses
Index recall is the share of the exact top k the index also returned. Cost is counted in distance computations, never in invented milliseconds.

The precedent corpus of the example starts small: 40 seeded decisions. This site's own case UW-R10 grows it to 4,000. Nothing about the stored vectors changes, and no budget changes either: the agent still asks for 50 candidates, reranks to 10 and puts 5 in the context. One number does change. The exact precedent search of the previous page compared 39 active rows per query; now it compares 3,999.

Someone proposes an index. The example builds a toy HNSW graph over all 4,000 vectors and asks it for the ten nearest precedents at its smallest search setting. The answer arrives after 77 distance computations instead of 3,999. Then the example compares it with exact search: on average across nine queries, the index found 67% of the true ten. A third of the nearest precedents were silently missing, and nothing in the result said so.

Raise the search setting and the index finds all ten, after 247 computations. Both runs were "the index"; one was fast and incomplete, the other slower and complete. This page explains what the index does when it skips rows, which knobs move it between those two runs, and how to measure, not assume, what it lost. All numbers here are from the example's toy code and toy data: they show the mechanism, not the quality of any model or product.

What this is not. An index is not a vector database: pgvector and sqlite-vec add indexes to general databases, and the ecosystems page compares engines. pgvector's own settings, operators and filter behavior are on pgvector. How index choices change at 100,000 or a million rows, and how to benchmark them, is on scale.

Exact or approximate: the trade in one sentence#

Exact search compares the query vector with every candidate row and returns the true top k. An approximate nearest neighbor index, an ANN index for short, is a data structure built over the vectors in advance that lets a query compare only a small share of them. It usually finds the true neighbors, and sometimes misses one.

The trade is recall against work. Work here means distance computations: how many times the query vector was compared with a stored vector. The example counts them because they are what an index saves, and because timing toy Python code would be a fake benchmark. Recall here means index recall: of the exact top k, the share the index also returned. If exact search says the ten nearest are rows 300, 201, 70 and seven others, and the index returns nine of those ten, its index recall@10 is 0.9.

Before AI. Engineers already accept approximate answers where exact ones cost too much: a dashboard that shows an approximate count of distinct visitors, a cache that serves a value a few seconds old. Each is chosen with the error stated and checked. An ANN index belongs in that family. A btree is different: it returns exactly the rows that match, because "equal to" and "between" follow one sort order. Closeness in 384 dimensions follows no single sort order, so an index must guess where to look.

One correction before the mechanics, because it appears in many documents: the index is HNSW, for Hierarchical Navigable Small World. "HSNW" is a common typo for the same thing. And HNSW is a data structure, never a model: the embedding model makes the vectors, and HNSW only organizes them.

HNSW: a layered graph you walk downhill#

Picture the 400 points of the lab below as towns on a map. Each town keeps roads to a few nearby towns. To find the towns nearest to some location, start anywhere, look at your neighbors, move to the one closest to the target, and repeat until no neighbor is closer. That is a greedy walk on a proximity graph: a graph in which every point links to some of its near neighbors.

A single graph has a problem: from a far start, the walk takes many small steps. HNSW adds express layers, the way a road network has highways above local streets. Every point is on the bottom layer, layer 0. A random, shrinking share of points also sits on layer 1, fewer on layer 2, and so on, each layer with its own links. The HNSW paper by Malkov and Yashunin (arXiv, 2016) describes exactly this: a hierarchy of proximity graphs over nested subsets, with each element's top layer drawn at random with exponentially decaying probability, and search starting at the top.

A search runs in two phases. First, greedy descent: on each upper layer, walk to the point closest to the query, then drop to the layer below and continue from there. Second, a beam search on layer 0: keep a list of the best candidates found so far, expand their neighbors, and stop when no unexplored candidate can improve the list. The beam's width is a search setting called ef_search. A wider beam explores more of the graph, finds more true neighbors, and computes more distances.

Diagram: An HNSW search: greedy descent through sparse layers, then a beam on layer 0

Read left to right. The search starts at the single entry point on the top layer and walks to the point closest to the query on each layer before dropping down. Layer 0 holds every point; there a beam of width ef_search explores neighbors until no candidate can improve the list. Numbers are from the example's 400-point toy graph (M 8, ef_construction 32) and its first lab query.

  1. Upper layers: express roads
    1. Entry point: Every search starts at the one point on the top layer.
    2. Greedy descent: On each layer, move to the neighbor closest to the query, then drop a layer.
  2. Layer 0: every point
    1. Beam search: Keep the best candidates found, expand their neighbors, stop when nothing improves.
  3. Result
    1. Approximate top 10: The ten best rows the beam saw; usually the true ten, sometimes not.

The diagram shows the walk on the example's 400-point graph. The upper layers move the search across the map in a few steps; layer 0 does the careful local search, and that is where ef_search decides how careful.

Two settings shape the graph when it is built, and one shapes each search.

M is the number of links each point keeps per layer. The hnswlib documentation, read on 2026-11-18, calls it the number of bi-directional links created for every new element, names 2 to 100 as a reasonable range, and estimates memory at about 8 to 10 bytes per M per element. More links make the graph harder to get lost in and cost memory and build time.

ef_construction is the beam width used while inserting each point, to find the neighbors it will link to. A wider beam at build finds better neighbors and makes a better graph, at the cost of build time and insert speed.

ef_search is the beam width at query time, the knob of the opening story. hnswlib notes that it must be at least k. pgvector names these m, ef_construction and hnsw.ef_search, with defaults 16, 64 and 40 as documented on 2026-11-18; the pgvector page has the DDL.

The script below builds two graphs over the lab's 400 points and runs one query: a reasonable graph (M 8, ef_construction 32) and a deliberately weak one (M 2, ef_construction 4). It prints how many points sit on each layer, the entry path of the greedy descent, the work and the index recall against exact search. A successful run shows the layers, the walk and how a weak graph loses a neighbor; it proves nothing about real data, where clusters, duplicates and 384 dimensions make recall harder to reach.

# hnsw_walk.py, run from a scratch copy of examples/rag-uw
from ann import HNSW, IVF, default_lab_set, exact_knn
from vecmath import l2

lab = default_lab_set()                      # 400 seeded 2-D points, 12 query points
pts, q = lab["points"], lab["queries"][0]
truth, exact_work = exact_knn(pts, q, 10)
print(f"exact scan: {exact_work} distance computations, true top 10 = {truth}")

for m, efc in ((8, 32), (2, 4)):
    h = HNSW(pts, M=m, ef_construction=efc, distance=l2)
    per_layer = [len(h.layers[i]) for i in range(h.max_level + 1)]
    print(f"\nHNSW M={m} ef_construction={efc}: nodes per layer (0 = all) {per_layer}, "
          f"build computations {h.build_computations}")
    for ef in (10, 40):
        got, work, info = h.search(q, 10, ef)
        found = len(set(got) & set(truth))
        print(f"  ef_search={ef:3d}: entry path {info['path']}, {work} computations, index recall@10 {found / 10:.1f}")

ivf = IVF(pts, lists=16)
for npb in (1, 4):
    got, work, info = ivf.search(q, 10, npb)
    print(f"IVF lists=16 nprobe={npb}: scanned lists {info['probed']}, {work} computations, "
          f"index recall@10 {len(set(got) & set(truth)) / 10:.1f}")
exact scan: 400 distance computations, true top 10 = [300, 201, 70, 374, 284, 12, 262, 289, 15, 397]

HNSW M=8 ef_construction=32: nodes per layer (0 = all) [400, 52, 7, 1], build computations 107715
  ef_search= 10: entry path [368, 368, 181, 300], 59 computations, index recall@10 1.0
  ef_search= 40: entry path [368, 368, 181, 300], 121 computations, index recall@10 1.0

HNSW M=2 ef_construction=4: nodes per layer (0 = all) [400, 222, 105, 52, 30, 16, 7, 3, 1, 1, 1, 1], build computations 22617
  ef_search= 10: entry path [368, 368, 368, 368, 368, 109, 181, 245, 70, 300, 300, 300], 46 computations, index recall@10 0.9
  ef_search= 40: entry path [368, 368, 368, 368, 368, 109, 181, 245, 70, 300, 300, 300], 86 computations, index recall@10 1.0
IVF lists=16 nprobe=1: scanned lists [14], 56 computations, index recall@10 1.0
IVF lists=16 nprobe=4: scanned lists [14, 15, 3, 6], 144 computations, index recall@10 1.0

Read the first graph. All 400 points are on layer 0, 52 on layer 1, 7 on layer 2 and one, the entry point 368, on top. The descent visits 368, then 181, then lands on 300, which is the true nearest neighbor. From there the beam finds all ten true neighbors after 59 distance computations, where exact search needed 400. A wider beam (ef_search 40) does 121 computations and gains nothing on this easy query.

Now the weak graph. With M 2 the toy's layer formula (1 / ln M) makes many more layers, and each point keeps so few links that the beam at ef_search 10 misses one true neighbor: index recall 0.9. Widening the beam to 40 recovers it. That is the trade in miniature, and the reason the build settings matter: a poor graph needs a wider search to reach the same recall. The build cost moves the other way: 22,617 computations for the weak graph, 107,715 for the reasonable one.

IVF: sort the rows into buckets, search the nearest few#

IVF, for inverted file, takes a different route. At build time it groups the vectors into clusters with k-means, an algorithm that places a number of centers and assigns each vector to its nearest center. Each cluster becomes a list of row ids. At query time it compares the query with the centers, picks the nearest few lists, and runs an exact scan inside them only.

The number of lists is a build setting (lists in pgvector, nlist in FAISS). The number of lists scanned per query is the search setting: nprobe in FAISS, ivfflat.probes in pgvector, where the default is 1, as documented on 2026-11-18. A true neighbor that sits in a list next door is missed when that list is not probed, which happens most often for queries near a cluster border. More probes find it and scan more rows. pgvector's README notes that setting probes to the number of lists makes the search exact, and the planner then stops using the index.

In the script above, 16 lists over the 400 points: one probe scans one list for 56 computations and happens to find all ten; four probes scan 144 rows. The 1,000-row run below shows a query set where one probe is not enough. "Flat" in IVFFlat means the vectors inside each list are stored and compared uncompressed, which matters for the quantization section below.

IVF needs data before it can build, because the centers are learned from the vectors. pgvector's README says to create an IVFFlat index after the table has data, and FAISS documents a train step for its IVF indexes. HNSW has no training step, so pgvector documents that an HNSW index can be created on an empty table.

The lab: exhaustive scan, graph walk and buckets#

The lab builds the same toy HNSW and IVF in the browser from the example's code, over 400 seeded 2-D points. Pick a method, a query, ef_search (10 to 160) or nprobe (1 to 16), a filter selectivity, and the layer to draw. It shows index recall@10 against exact search, the number of distance computations (work, not latency), the missed neighbors and the greedy walk down the layers. Everything is illustrative toy data.

The same numbers without JavaScript (query 1, k = 10, M 8 graph; an exact scan costs 400 computations, 17 with the 5% filter; in this example):

Method and settingRows returnedIndex recall@10Distance computations
HNSW, ef_search 10101.059
HNSW, ef_search 40101.0121
HNSW, ef_search 160101.0228
IVF, nprobe 1101.056
IVF, nprobe 4101.0144
5% filter, HNSW ef_search 40, post-filter30.3121
5% filter, HNSW ef_search 160, post-filter70.7228
5% filter, HNSW ef_search 40, iterative scan101.0817
5% filter, exact scan of the filtered rows101.017

The last four rows are this site's case UW-R09 and belong to the next section.

The measurement has four steps, and the exact search page supplies the first. Take a set of queries that looks like real traffic. For each one, compute the exact top k: the ground truth. Run the same query through the index. Count how many of the exact rows the index returned, divide by k, and average over the queries. Report the work next to it, and the queries that returned fewer than k rows.

ann.py does this over 1,000 points in 16 dimensions with 20 queries, sweeping ef_search and nprobe. A successful run proves that recall and work move together as the search widens; it does not predict the numbers for any real dataset or engine.

cd /tmp/rag-uw && /opt/homebrew/bin/python3 ann.py --n 1000 --dim 16
HNSW n=1000 dim=16: build distance computations 400850, layers 4
  ef_search=   1  index recall@10=0.990  distance computations=102 (exact 1000)
  ef_search=   4  index recall@10=0.990  distance computations=102 (exact 1000)
  ef_search=  10  index recall@10=0.990  distance computations=102 (exact 1000)
  ef_search=  20  index recall@10=1.000  distance computations=128 (exact 1000)
  ef_search=  40  index recall@10=1.000  distance computations=147 (exact 1000)
  ef_search=  80  index recall@10=1.000  distance computations=155 (exact 1000)
  ef_search= 160  index recall@10=1.000  distance computations=284 (exact 1000)
  IVF nprobe=  1  index recall@10=0.615  distance computations=90
  IVF nprobe=  2  index recall@10=0.845  distance computations=128
  IVF nprobe=  4  index recall@10=0.980  distance computations=183
  IVF nprobe=  8  index recall@10=1.000  distance computations=282
  IVF nprobe= 16  index recall@10=1.000  distance computations=510
  IVF nprobe= 32  index recall@10=1.000  distance computations=1032

Two things stand out. The first three HNSW lines are identical because the toy widens the beam to at least k (max(ef_search, k)): an ef_search below k is quietly raised. pgvector behaves differently and returns at most ef_search rows, a cap the pgvector page explains. And the IVF lines show the trade at its clearest: one probe out of 32 lists finds 61.5% of the true neighbors for 90 computations; eight probes find all of them for 282. Probing all 32 lists costs more than exact search, because the query also compares itself with the 32 centers.

The same check runs on PostgreSQL. Q11 in the example's sql/queries.sql stores the exact top 10 for one query over a 20,000-row toy table with index scans off, then runs the HNSW index at three ef_search values and joins the results. One run on one laptop, toy data; not a benchmark (PostgreSQL 16.14, pgvector 0.8.3, from sql/OUTPUT.md):

-- Q11 from examples/rag-uw/sql/queries.sql, abridged here to one ef_search; the complete Q11 (10, 40, 100) ran
-- on the throwaway database on 2026-11-18 and printed the output below
SET enable_indexscan = off;
CREATE TEMP TABLE exact_top AS
  SELECT id FROM scale_points ORDER BY embedding <=> :'sq'::vector(16) LIMIT 10;
RESET enable_indexscan;
SET enable_seqscan = off;
SET hnsw.ef_search = 10;
CREATE TEMP TABLE ann_10 AS SELECT id FROM scale_points ORDER BY embedding <=> :'sq'::vector(16) LIMIT 10;
SELECT 10 AS ef_search, count(*) / 10.0 AS index_recall_at_10 FROM ann_10 JOIN exact_top USING (id);
 ef_search |   index_recall_at_10   
-----------+------------------------
        10 | 1.00000000000000000000
        40 | 1.00000000000000000000
       100 | 1.00000000000000000000

Recall 1.0 at every setting is one query on uniform toy data, and it says little: the measurement is easy where the data is easy. Its value is the procedure, which is the same on a real table with a real query set.

Common confusion. Index recall measures the index against exact search, not retrieval against the truth. An index with index recall 1.0 returns exactly what exact search returns, including any wrong rows exact search ranks high. Whether those rows answer the question is recall@k against human labels, computed on the evaluation page.

Filters: a beam that is mostly the wrong rows#

An approximate index answers "which rows are near the query". A filter answers "which rows are allowed". In the example's toy, as in pgvector's documented behavior, the filter is applied after the index search. The beam collects about ef_search near rows; then the filter removes the ones that fail.

That works when most rows pass. It fails when few do. In UW-R09 only 17 of 400 points pass a 5% filter. The beam at ef_search 40 holds 40 near points, and on average only about two of them pass, so the query asks for ten rows and gets three. pgvector's README gives the same arithmetic as an example: with 10% of rows matching and ef_search 40, about 4 rows match on average. The lab table above shows the fixes side by side: a wider beam (7 rows at 160), an iterative scan that keeps searching until enough rows pass (10 rows, 817 computations), or an exact scan of the 17 filtered rows (10 rows, 17 computations).

The last line deserves a second look. With a selective filter, exact search over the filtered rows did less work than any index setting. The pgvector page shows how the database settings and the query planner make this choice, including a run where the HNSW query returned zero rows.

Quantization: smaller vectors, approximate distances#

An index can skip rows; it can also make each row cheaper to compare and store. Quantization stores a vector in fewer bits than the original, at the cost of distances that are slightly off. Two forms are worth knowing as concepts.

Scalar quantization replaces each 4-byte float with a smaller number: one byte per dimension in FAISS's SQ8, as documented on 2026-11-18. A 384-dimensional float32 vector holds 1,536 bytes of values; at one byte per dimension it holds 384 (arithmetic, illustrative). pgvector's halfvec type, two bytes per dimension, is a milder relative of the same idea, covered on pgvector.

Product quantization goes further. FAISS's documentation describes it as splitting each vector into sub-vectors and quantizing each to a few bits, usually 8: each sub-vector is replaced by the id of the nearest entry in a small learned codebook, and the code takes ceil(M × nbits / 8) bytes per vector, where M here counts sub-vectors (not HNSW links). Split 384 dimensions into 48 sub-vectors of 8 at 8 bits each, and a vector becomes 48 bytes (illustrative). IVF and product quantization combine in FAISS's IndexIVFPQ: buckets to skip rows, short codes to compare the rest.

The cost is accuracy. A distance computed on codes is an estimate, so near-ties reorder and true neighbors drop out. The common repair, documented by pgvector for its binary quantization example, is to fetch more candidates than needed with the compressed vectors and re-rank them by the original ones.

ScaNN, named#

ScaNN (Scalable Nearest Neighbors) is a library from Google Research. Its repository, read on 2026-11-18, describes search-space pruning plus quantization for maximum inner product search, with other distances such as L2 also supported, and cites the anisotropic vector quantization paper (ICML 2020) and SOAR (NeurIPS 2023). Google Cloud's Vector Search overview says that product is built on ScaNN, and AlloyDB documents an alloydb_scann extension with a scann index type. The product details live on Google Cloud. For this page, ScaNN is a third family next to graphs and buckets: partition the space, compress, then rescore.

The index lifecycle: build, insert, delete, rebuild#

An index is a structure next to the table, and it has a life of its own.

Build. The graph or the lists are built from the vectors present. The build is the expensive moment: the toy's reasonable graph took 107,715 distance computations for 400 points. pgvector documents faster HNSW builds when the graph fits in maintenance_work_mem, and IVFFlat builds only once data exists.

Insert. A new row in HNSW is inserted like every other point: a beam search at ef_construction finds its neighbors and links it in, so inserts are slower than in a plain table. In IVF a new row goes into the list of its nearest center. The centers were learned from the data at build time; if new data drifts away from them, lists become uneven and recall at the same nprobe can fall. That is a design consequence; the pgvector README, in the parts read, says when to build an IVFFlat index but not when to retrain one.

Delete. Removing a point from a graph cuts the roads through it. FAISS's documentation states that its HNSW index does not support removing vectors, because that would destroy the graph structure. pgvector, inside PostgreSQL, handles deleted rows through vacuuming, and its changelog records fixes in 0.8.3 and 0.8.4 for HNSW vacuuming and graph repair.

Rebuild. Rebuilding the index from the same vectors is a reindex. It is the fix for a degraded graph, drifted lists or new build settings. It is not a re-embedding, which recomputes the vectors after a model or content change, and one never substitutes for the other. UW-R10 grew the table a hundredfold with no re-embedding; whether to build or rebuild an index was measured.

Diagram: Every index decision is a measured loop against exact search

Read left to right. Build the index with chosen settings. Run a realistic query set through it and through exact search. Index recall is the share of the exact top k the index returned, reported next to the work it saved. Change a search setting, rebuild with other build settings, or keep exact search, only on the measured result. A rebuild is a reindex: the vectors stay the same.

  1. Build
    1. Build the index: The structure is made from the vectors present; this is the expensive moment.
  2. Query both ways
    1. Index search: Compares a small share of rows and may miss true neighbors.
    2. Exact search: The true top k for the same query: the answer key.
  3. Decide on numbers
    1. Index recall and work: Report recall, work and short results together; never one without the others.
    2. Tune, rebuild or stay exact: Change a setting or rebuild with the same vectors only when the measurement says so.

The diagram is the loop every index decision goes through: build with settings, query, compare with exact search, and change a setting or rebuild only when the measured recall says so.

In the insurance build. In that build, the applicant-profile corpus has an HNSW index with m = 16 and ef_construction = 64, queries run with hnsw.ef_search = 80, and hnsw.iterative_scan = relaxed_order is set when pgvector is 0.8 or later, followed by a re-sort. The precedent corpus has no ANN index: a btree and an exact distance sort, with HNSW noted in its schema as worth considering only past about 50,000 rows per provision.
In a coding agent. A coding agent that keeps an embedding index of a repository meets the lifecycle every day. A refactor deletes and moves hundreds of chunks; in a graph index those become deletions and inserts, and a stale graph keeps routing searches through removed chunks until it is repaired or rebuilt. Rebuilding the index after a large refactor is a reindex; switching the agent to a new embedding model is a re-embedding of every chunk.

How indexes fail, and the check for each#

Recall assumed instead of measured. A default setting returned 67% of the true neighbors in UW-R10 at ef_search 10. Measure index recall on your queries.

ef_search below k. pgvector returns at most ef_search rows; ask for 50 candidates with the default 40 and you get 40 at most.

A selective filter after the index. Three rows where ten were asked for (UW-R09). Use an iterative scan, a wider beam, or exact search over the filtered rows.

Measured on easy data. Q11's recall 1.0 is one query on uniform toy vectors. Real embeddings cluster and repeat.

Latency quoted from a toy. Count work in distance computations here; time a real engine on real hardware on the scale page's terms.

Production pitfall. An index changes results without raising an error. A deploy that adds an HNSW index or lowers ef_search can drop true neighbors from every query, and the agent keeps writing confident recommendations from what remains. Put an index-recall check against exact search in the release checks, next to the retrieval metrics.

A checklist for Monday#

QuestionWhy it matters
Do you know the rows left after your filters, per query?Few rows: exact search may do less work than any index
Is index recall measured against exact search on a realistic query set?Defaults can miss a third of the neighbors silently
Is ef_search at least the number of candidates you ask for?pgvector returns at most ef_search rows
For IVF, was the index built after the data, and is probes above 1?One probe misses neighbors in the next list
Is cost reported as work, with timings only from a real engine?Toy timings are not a benchmark
Is a rebuild (reindex) planned separately from a model change (re-embed)?They fix different problems
If vectors are quantized, are candidates re-ranked by full vectors?Compressed distances reorder near-ties
Why toy recall is high and real recall is notClusters, duplicates, dimension and the query set

The toy runs on this page reach index recall 1.0 easily. Three properties of real embedding data make that harder.

Real vectors cluster unevenly. Many chunks of the same policy document, or many near-identical applicant profiles, sit in dense pockets, and the true ten nearest neighbors of a query in such a pocket are separated by tiny distances. A beam that reaches the pocket can still return a slightly different ten. Duplicates are the extreme case: with identical vectors, several sets of ids are equally correct, which is why the example's index_recall is tie-aware and counts a row whose distance is no larger than the k-th exact distance.

Dimension matters too. The toy's 2-D and 16-D points are friendly; in 384 dimensions, distances between random points concentrate and the graph's shortcuts help less. And the query set matters most. Queries drawn from the same distribution as the data, as in ann.py, are easier than real traffic, which includes odd, short and out-of-domain questions. Measure with queries logged from real use, sliced by the filters they carry; the evaluation page covers slices.

What an HNSW index costs in memory, as arithmeticLinks per point, vectors per row, and where quantization helps

hnswlib's documentation estimates the graph's memory at about 8 to 10 bytes per M per element. For an illustrative 1,000,000 rows at M 16, that is about 128 to 160 MB for the links alone. The vectors themselves are larger: pgvector's vector type takes 4 bytes per dimension plus 8, so 384 dimensions take 1,544 bytes per row, about 1.5 GB for a million rows. These are calculations from documented figures, not measurements of any system, and an engine adds its own overheads.

Two conclusions follow. First, M is rarely the memory problem; the stored vectors are. Second, that is where quantization pays: one byte per dimension cuts the vector part by about four times, and product quantization by much more, at a measured cost in recall. pgvector's README documents faster HNSW builds while the graph fits in maintenance_work_mem and raises a notice when it no longer fits, which makes build memory a planning number, not a surprise.

Graphs, partitions and disk: competing index designsWhat each family is good at, as documented

The families on this page differ in what they optimize. Graph indexes such as HNSW give a good speed-recall trade and support inserts without retraining; pgvector's README says HNSW has slower builds and more memory than IVFFlat but a better speed-recall trade. Partition indexes such as IVF build faster and smaller, need training data, and lose recall at cluster borders unless more lists are probed. Quantized partitions such as IVF with product quantization or ScaNN shrink memory most and rescore to recover accuracy.

A fourth family keeps the index on disk instead of in memory. DiskANN-style indexes are named in several products' documentation read for this site: Milvus lists a DISKANN index type, OpenSearch names a DiskANN-style engine through a plugin, and sqlite-vec's v0.1.10 alpha releases mention DiskANN features. The ecosystems page has the sourced matrix.

The choice is not a ranking. A small, filtered corpus may need no index at all; a large one with frequent inserts favors a graph; a very large, mostly static one may favor partitions with compression. The decision belongs to measurements on the scale page.

Deletes, updates and graph repairWhy a graph index degrades between rebuilds

An update to a vector is a delete plus an insert. In a graph, the deleted point was a waypoint: other points linked to it, and searches passed through it. Removing it without repair leaves routes that lead nowhere, and searches that used to pass through that region now reach fewer good candidates. Marking it deleted but keeping it as a waypoint preserves routes and wastes work on rows that can never be returned.

Databases handle this differently, and the documentation is the place to look. FAISS states that its HNSW index cannot remove vectors. pgvector relies on PostgreSQL's vacuum to clean up, its README suggests reindexing before vacuuming an HNSW index because vacuum can take a while, and its changelog records fixes in 0.8.3 (possible index corruption with HNSW vacuuming) and 0.8.4 (an "hnsw graph not repaired" error). The general lesson: after heavy churn, measure index recall again; if it fell, a rebuild with the same vectors (a reindex) restores the graph. The precedent corpus of the insurance example, with its pending, active, quarantined and revoked statuses, is exactly such a churning table.

In one breath#

An ANN index is a structure built over the vectors that lets a query compare a small share of the rows, and it can miss true neighbors while doing so. HNSW walks a layered graph downhill and searches layer 0 with a beam of width ef_search; IVF scans the nprobe nearest of its k-means lists; quantization shrinks each vector at the cost of approximate distances. Every setting moves recall and work together, so the only honest statement about an index is a measured one: index recall against exact search, on realistic queries, next to the work it saved.

The precedent search of UW-R10 can now skip most of its 4,000 rows, and the example measured the price at each setting instead of trusting a default. One risk remains open: a selective filter made the index return three rows where ten were asked for. The next page, PostgreSQL and pgvector, runs that failure on a real database, where the HNSW query returns zero rows, and shows the settings, plans and indexes that fix it.