What a Vector Index Actually Costs: The Router, the Quantiser, and the Recall Ceiling

The NeurIPS'21 Billion-Scale Approximate Nearest Neighbor Search challenge made an unusual choice for its leaderboard. Rather than letting entrants pick an operating point, the organisers fixed query throughput at 10,000 queries per second on a 32-vCPU Azure VM and ranked submissions purely on the recall they could sustain there. The strongest standard-hardware entries came in around 0.71 to 0.79 recall@10 on the billion-point BIGANN, DEEP and MS Turing sets (Simhadri et al., 2022, Results of the NeurIPS'21 Challenge on Billion-Scale ANN Search, PMLR 176). Tuned submissions from specialist teams, and one query in four or five still missed a true neighbour.

That is the honest shape of the problem, and it is routinely hidden. A benchmark reporting only queries per second is reporting half a number.

Why this matters: Every ANN index is a router (which vectors do I even look at?) bolted to a quantiser (how lossy is each comparison?). The quantiser sets your recall ceiling; the router sets how fast you approach it. Teams that confuse the two spend weeks raising ef_search against a ceiling a 96-byte code imposed at build time, or rebuild a perfectly good graph to fix something a rescore pass would have solved in an afternoon.

TL;DR

• A vector index is two decisions, not one. Routing picks the candidate set; quantisation decides how accurately candidates are scored. They fail differently and are tuned at different times.
• Compression is where the ceiling lives. RaBitQ's authors note the method "can hardly produce reasonable recall" without re-ranking (Gao & Long, SIGMOD 2024), and FAISS pairs PQ with a refinement step for the same reason (FAISS wiki).
• Both halves cost memory, in different proportions. A 768-dim float32 vector is 3,072 bytes; PQ96 stores it in 96 and RaBitQ in d/8 + 8 = 104, while HNSW32 adds about 256 bytes of links on top (FAISS wiki, The index factory). Those links are 8% of a float32 vector and the dominant cost over a 14-byte code.
• DiskANN's headline result is a rescore result: 95%+ 1-recall@1 on billion-point SIFT1B from a 64 GB machine, where comparable methods at similar footprint plateau near 50% (Subramanya et al., NeurIPS 2019). Compressed codes navigate; the SSD read scores.
• ef_search and nprobe are runtime parameters; M, nlist and the code size are build-time commitments. Only one of those sets can be changed during an incident, and neither has an alarm for codebook drift.

At a Glance

flowchart LR
    Q[Query vector] --> R{Router}
    R -->|graph traversal<br/>or cell probing| C[Candidate set<br/>10 to 1000 ids]
    C --> S[Score with<br/>compressed codes]
    S --> T[Shortlist<br/>k times k_factor]
    T --> X[Rescore with<br/>full vectors]
    X --> K[Top-k answer]

    D1[ef_search / nprobe<br/>runtime dial] -.-> R
    D2[code size / bits<br/>build-time ceiling] -.-> S
    D3[rescore budget<br/>runtime dial] -.-> X

    classDef blue fill:#1e40af,stroke:#3b82f6,stroke-width:1px,color:#fff
    classDef purple fill:#6d28d9,stroke:#a78bfa,stroke-width:1px,color:#fff
    classDef teal fill:#0e7490,stroke:#22d3ee,stroke-width:1px,color:#fff
    classDef amber fill:#b45309,stroke:#fbbf24,stroke-width:1px,color:#fff
    classDef slate fill:#334155,stroke:#64748b,stroke-width:1px,color:#e2e8f0

    class Q,C blue
    class R,S,T purple
    class X,K teal
    class D1,D3 slate
    class D2 amber

Everything entering the router is a latency decision you can revisit per query. Everything entering the scorer is a fidelity decision made at build time.

Before the Graph Won

Approximate nearest neighbour search spent the 2000s trying to be a tree problem. Dimensionality defeated that: above roughly 20 dimensions, space-partitioning trees visit so many branches that they lose to a linear scan. The field split instead along the two axes above, compression first.

timeline
    title How the two halves of a vector index were invented
    2011 : Jegou, Douze and Schmid publish product quantisation
         : IVFADC pairs a coarse cell index with compressed residuals
    2013 : Ge et al. add a learned rotation before the subspace split, OPQ
    2016 : Malkov and Yashunin publish HNSW
         : A layer hierarchy plus a neighbour-selection heuristic for clustered data
    2019 : NSG shows a monotonic relative neighbourhood graph beats earlier graphs
         : DiskANN and Vamana put a billion points on one 64 GB node with an SSD
    2020 : ScaNN changes only the quantisation loss and doubles QPS at fixed accuracy
         : ANN-Benchmarks makes the recall-versus-QPS curve the standard figure
    2021 : SPANN reaches 90 percent recall in about a millisecond from a memory-disk hybrid
         : The NeurIPS billion-scale challenge ranks on recall at fixed throughput
    2023 : Filtered-DiskANN builds label predicates into the graph edges
    2024 : RaBitQ gives binary quantisation a provable error bound

Product quantisation arrived from image retrieval, as a way to fit a hundred million SIFT descriptors in RAM (Jégou, Douze & Schmid, 2011, Product Quantization for Nearest Neighbor Search, IEEE TPAMI 33(1):117–128). That paper already shipped the two-part structure under the name IVFADC: a coarse quantiser to pick cells, a product quantiser to score what is inside them. Everything since has been a better router, a better quantiser, or a better way to recover from one. Optimised product quantisation followed, learning an orthogonal rotation so the fixed subspace split lands on axes of comparable variance (Ge, He, Ke & Sun, CVPR 2013), at no per-vector serving cost.

The graph era began with HNSW (Malkov & Yashunin, IEEE TPAMI 42(4):824–836, preprint arXiv:1603.09320), whose two contributions get collapsed into one. The exponentially-decaying layer hierarchy gives logarithmic-ish navigation from a fixed entry point; a separate neighbour-selection heuristic chooses which candidate links to keep. The authors single out that heuristic as what lifts performance at high recall and on highly clustered data, exactly the regime real embedding corpora live in. A graph built from each node's nearest M neighbours is worse than one built from a diverse M, because nearest-only links collapse into cliques with no bridges out.

DiskANN then reframed the memory question: not how to shrink an in-memory graph, but what belongs in memory at all. Compressed codes navigate, full vectors on SSD do the final scoring. A billion points served from one workstation with 64 GB of RAM at over 5,000 QPS, mean latency under 3 ms, 95%+ 1-recall@1 on SIFT1B, where FAISS and IVFOADC+G+P at comparable footprint levelled off near 50% (Subramanya et al., NeurIPS 2019). That 50-versus-95 gap is the clearest evidence in the literature for the argument here: similar routers, similar memory, different answers to quantisation error.

[IMAGE: Two-panel scatter plot of recall@10 versus queries per second, log x-axis. Left panel: three HNSW curves at M=8, 16, 32 over full-precision vectors, all converging toward recall 0.99 at low QPS. Right panel: the same three curves over PQ96 codes with no rescoring, flattening between recall 0.82 and 0.88 no matter how far right you go. Caption: "Raising the routing budget moves you along a curve. Changing the quantiser moves the curve."]

The Router and the Quantiser

What routing actually is

Every ANN search is a bounded traversal that hopes the true neighbours are reachable from where it starts. Graph and cell indexes differ in what "reachable" means.

A graph index does best-first search: start at a fixed entry point, keep a priority queue of the ef closest candidates seen, repeatedly expand the nearest unexpanded one and score its out-neighbours, stop when the queue's nearest unexpanded candidate is further than the worst member of the result set. Distance computations run at roughly ef times the average out-degree, so HNSW at M = 16 and ef_search = 40 costs a few hundred to a couple of thousand comparisons per query against a corpus of any size. That size-independence is the whole appeal.

A cell index is blunter. Train nlist centroids, assign each vector to its nearest, then score the query against all centroids and exhaustively scan the nprobe nearest lists. The comparison count is nlist + nprobe × N/nlist, minimised near \(\sqrt{N}\), which is why FAISS recommends nlist between \(4\sqrt{N}\) and \(16\sqrt{N}\), with recipes of IVF65536_HNSW32 for 1M–10M vectors and IVF1048576_HNSW32 for 100M–1B (FAISS wiki, Guidelines to choose an index). Note the suffix: at a million centroids, finding the nearest cells is itself an ANN problem, so the coarse quantiser gets its own graph index. Routers nest, which is a sign that "graph versus cell" was never the real question.

HNSW in the detail that matters

Three parameters, and they are not peers.

M is the maximum out-degree per layer, with layer 0 allowed roughly 2M because it is the only layer holding every point. It is a build-time commitment and the source of graph memory: FAISS documents HNSW32 at about 256 bytes per vector at the densest level, exactly \(32 \times 2 \times 4\) bytes of 32-bit neighbour ids (FAISS wiki, The index factory). hnswlib and pgvector both default to M = 16, giving 128 bytes.

[IMAGE: Three-layer HNSW cutaway. Top layer: five nodes with long edges spanning the whole width. Middle layer: twenty nodes, medium edges. Bottom layer: all points, dense short edges. A dashed query path descends through the layers, taking two hops at the top and six at the bottom. A second inset shows the same bottom layer built from nearest-only links, with three visibly disconnected cliques. Caption: "The hierarchy shortens the walk. The neighbour-selection heuristic is what keeps the cliques connected at all."]

ef_construction is the candidate-queue width during insertion, and it buys graph quality with build time and nothing else (hnswlib defaults to 200, pgvector to 64). If you are going to be careless about one parameter, be careless about this one in the generous direction: a better graph is free at query time.

ef_search is the candidate-queue width at query time, and the only genuinely elastic dial in the system. pgvector defaults it to 40, and tells you to leave m and ef_construction alone unless recall is low (pgvector README). Being a session-level setting, it lets you serve a premium tenant at 400 and a batch backfill at 20 against one index, and raise it mid-incident without rebuilding. Nothing else here has that property.

The neighbour-selection heuristic has no knob and the most consequence. Given more than M candidate links, it prefers candidates not already well-connected to each other, approximating a relative neighbourhood graph and preserving long-range bridges. NSG makes the same move explicitly, constructing a monotonic relative neighbourhood graph so a greedy walk has a monotone path to the target (Fu, Xiang, Wang & Cai, PVLDB 12(5):461–474). Vamana, DiskANN's graph, generalises it with an alpha parameter controlling how aggressively near-duplicate edges are pruned in favour of distant ones.

The quantiser as a lookup table

Product quantisation splits a \(d\)-dimensional vector \(x\) into \(m\) contiguous subvectors of dimension \(d/m\), quantising each independently against its own learned codebook \(\mathcal{C}^j\) of \(2^b\) centroids. The stored code is \(m\) integers of \(b\) bits, so per-vector cost is \(mb/8\) bytes regardless of \(d\).

What makes this fast, not merely small, is asymmetric distance computation. The query is never quantised. You precompute one table

and then the approximate squared distance to any stored code is

which is \(m\) lookups and \(m\) additions per candidate. For \(m = 96\) and \(b = 8\) the table is 96 × 256 floats, about 98 KB, built once per query and reused across every candidate. The symmetric variant, which quantises the query too, is cheaper to set up and strictly worse: it adds the query's own error to every comparison for no benefit once the table cost is amortised.

The modern refinement shrinks \(b\) rather than \(m\). At \(b = 4\) a subspace codebook fits in a SIMD register, so a batch of candidates resolves in parallel; FAISS exposes this as the fs fast-scan variants, where PQ28x4fs costs about 14 bytes per vector. RaBitQ pushes to one bit per dimension with a random rotation, costing about \(d/8 + 8\) bytes and, unlike PQ, carrying a sharp theoretical error bound (Gao & Long, SIGMOD 2024).

Why the quantiser is a ceiling and the router is not

Routing errors are recoverable by spending more time. Quantisation errors are not recoverable at all, except by reading something you did not store.

If the router never visits the true nearest neighbour, raising ef_search or nprobe visits more of the corpus and eventually visits it; recall against work is monotone and, in the limit, reaches 1.0. If the router does visit the true neighbour but the compressed code scores it below a decoy, no amount of extra probing helps: the comparison itself is wrong, and wrong the same way every time. More candidates make it worse, because each one is another chance for a lucky decoy to win.

Which is why every serious compressed index is two-stage. FAISS wraps compressed indexes in Refine(...) with a k_factor controlling how many candidates get exact rescoring; pgvector's binary-quantisation recipe states plainly that re-ranking with the original vectors improves recall; DiskANN's design is the rescore, and its 50-versus-95 gap against similar-memory baselines is a statement about rescoring rather than graph quality.

So a recall plateau as you raise the runtime dials means you are at the quantiser's ceiling, and the fixes are a larger code or a bigger rescore budget. Recall that climbs steadily at unaffordable latency means the quantiser is fine and the router is underfunded.

[IMAGE: Diagram of asymmetric distance computation. Top: a 768-dim query split into 96 blocks of 8 dims, each block fanning out to a 256-entry lookup table column. Bottom: a stored 96-byte code as 96 integer cells, arrows selecting one cell per table column into a summation node producing the approximate distance. Caption: "The query is never compressed. One 98 KB table, built per query, scores every candidate in 96 lookups."]

Seeing It in Motion

Routing geometry first: two structures, two distinct failure modes.

flowchart TB
    subgraph G["Graph router: HNSW"]
        GE[Entry point<br/>top layer] --> GA[Greedy descent]
        GA --> GB[Best-first queue<br/>width ef_search]
        GB --> GC[Expand nearest<br/>score out-neighbours]
        GC --> GB
        GC --> GF["Failure: a true neighbour<br/>sits behind a pruned bridge"]
    end

    subgraph C["Cell router: IVF"]
        CE[Score query against<br/>nlist centroids] --> CA[Pick nprobe<br/>nearest cells]
        CA --> CB[Exhaustive scan<br/>inside those cells]
        CB --> CF["Failure: query on a cell boundary<br/>neighbour in cell nprobe plus one"]
    end

    classDef purple fill:#6d28d9,stroke:#a78bfa,stroke-width:1px,color:#fff
    classDef blue fill:#1e40af,stroke:#3b82f6,stroke-width:1px,color:#fff
    classDef rose fill:#be123c,stroke:#fb7185,stroke-width:1px,color:#fff

    class GE,GA,GB,GC purple
    class CE,CA,CB blue
    class GF,CF rose

Graph routers fail on connectivity: the answer is indexed but unreachable within the traversal budget. Cell routers fail on geometry: the answer is in a cell you did not open, with a probability driven by how close the query sits to a Voronoi boundary, which in high dimensions is "usually". That is why IVF needs higher nprobe than its arithmetic suggests.

Now the two-stage path, with the disk read that makes DiskANN work.

sequenceDiagram
    participant Q as Query
    participant M as In-memory graph<br/>plus PQ codes
    participant D as SSD<br/>full vectors
    participant R as Rescorer
    Q->>M: embed, enter at fixed node
    loop beam search, budget L
        M->>M: expand node, score neighbours from PQ table
        M->>D: prefetch full vectors for beam front
    end
    Note over M,D: navigation uses compressed codes only<br/>disk I/O overlaps traversal
    M->>R: candidate ids, k times k_factor
    D->>R: full-precision vectors for candidates
    R->>R: exact distances, reorder
    R->>Q: top-k

Two details are easy to miss. Prefetch overlaps I/O with traversal, so a design that looks I/O-bound is not; and the rescorer, not the router, decides the final ordering, which is what licenses aggressive codes.

Finally the lifecycle, because most production recall incidents are lifecycle problems rather than tuning problems.

stateDiagram-v2
    [*] --> Training: sample corpus
    Training --> Built: codebooks and centroids frozen
    Built --> Serving: index loaded
    Serving --> Serving: insert, link into graph
    Serving --> Degraded: deletes become tombstones
    Degraded --> Serving: compaction reclaims slots
    Serving --> Stale: corpus distribution drifts
    Stale --> Training: retrain codebooks, full rebuild
    Degraded --> Training: fragmentation past threshold
    Serving --> [*]: decommission

The edge with no automatic trigger is Serving --> Stale.

Watch It Run

By the Numbers

Storage per vector, and what it means for 100 million 768-dimensional embeddings. The per-vector column is documented behaviour; the corpus column is arithmetic on top of it.

Sources: per-vector figures from the FAISS index factory and index-selection guidelines, which document HNSW32 link overhead at about 256 bytes, NSG32 at about 128, IVF id overhead at about 8, and RaBitQ at \(d/8 + 8\); pgvector documents \(4 \times \text{dims} + 8\) bytes for vector and \(\text{dims}/8 + 8\) for bit (pgvector README). The 100M column is multiplication, not measurement: real deployments add id maps, deleted-slot headroom, page overhead and replica count, so treat the usual 1.5x to 2x planning multiplier as an estimate.

Reported operating points, each from the system's own authors and therefore a claim rather than an independent measurement:

Sources: DiskANN, NeurIPS 2019; SPANN, NeurIPS 2021; Guo et al., ICML 2020, PMLR 119:3887–3896, with the QPS ratio as stated in Google's announcement of the ScaNN implementation. The ScaNN figure is a ratio at matched accuracy, not an absolute throughput, and the challenge figures are leaderboard entries on specific datasets, not a general bound.

[IMAGE: Horizontal stacked bar chart, one bar per configuration from the storage table, 100M-vector corpus in GB on a log x-axis. Each bar split into payload (vectors or codes) in blue and structural overhead (graph links, ids) in amber. The HNSW32,Flat bar is longest; the PQ28x4fs bar is a sliver with a proportionally large amber segment. Caption: "At 768 dimensions graph links are 8% of the bill. Over 14-byte codes, they are the bill."]

A Concrete Example

A support-knowledge corpus: 50 million chunks, 768-dimensional embeddings, 300 queries per second at peak, k = 10, and a hard floor of 0.95 recall@10 because the downstream reranker can only reorder what it is given.

Step 1: price the exact baseline. \(50 \times 10^6 \times 3072\) bytes = 153.6 GB of payload. Exact search over that at 300 QPS is 46 TB/s of memory bandwidth. Not happening.

Step 2: price HNSW over full vectors. M = 16 means about 128 bytes per vector of links, so 153.6 + 6.4 = 160 GB. At ef_search = 40 and out-degree near 16, expect 640 to 2,000 distance computations per query, each 768 multiply-adds: roughly 0.5 to 1.5 MFLOP. Trivially servable, and it clears 0.95 recall@10 comfortably. It also costs 160 GB of RAM per replica to serve a corpus whose text is perhaps 25 GB.

Step 3: price the compressed path. Switch to OPQ96_768,IVF16384,PQ96. With \(\sqrt{N} \approx 7{,}071\), FAISS's band puts the sensible nlist range at roughly 28,000 to 113,000; 16,384 is deliberately low to keep the training set modest, and we pay for that in nprobe. Storage becomes \(50 \times 10^6 \times (96 + 8)\) = 5.2 GB, plus 16,384 centroids at 3 KB each. The index is now 5.3 GB.

Step 4: count the comparisons. Cells hold \(50 \times 10^6 / 16{,}384 \approx 3{,}052\) vectors each. At nprobe = 32 the scan covers \(32 \times 3{,}052 \approx 97{,}700\) candidates, each scored by 96 table lookups: about 9.4 million lookups per query. That is 50x more comparison work than the HNSW path, but each comparison is a byte-indexed table read rather than a 768-dimensional dot product, over a 5.2 GB working set.

Step 5: find the ceiling. Suppose measurement gives 0.86 recall@10 at nprobe = 32. Raise to 64: 0.89. To 128: 0.90. To 256, scanning 780,000 candidates: 0.905. The flatness is the diagnosis. The router is visiting a sixth of the corpus for four points of recall, because the 96-byte code cannot separate rank 10 from rank 30 for this embedding distribution, and probing further only adds decoys.

Step 6: add the rescore and watch the ceiling move. Back to nprobe = 32, wrap the index in a refinement step over full-precision vectors at k_factor = 10, so the compressed stage returns 100 candidates and the rescorer computes exact distances on those. Cost: about 77 kFLOP, plus 100 random reads of 3,072 bytes. On NVMe that is 100 page reads: serialised at 100 µs each it is 10 ms, at queue depth 32 closer to 0.5 ms. Recall@10 goes to roughly 0.96, because the compressed stage only ever needed to get the true top-10 inside a 100-candidate shortlist, a far weaker requirement than ranking them correctly.

Step 7: read the bill. 5.3 GB of RAM for the index, 153.6 GB of full vectors on NVMe touched 100 pages at a time, 0.95+ recall@10, single-digit milliseconds. Against step 2's 160 GB per replica that is roughly a 30x reduction in the expensive resource, and the change that moved recall from 0.905 to 0.96 was not a router parameter at all. Four rounds of nprobe tuning bought four points; one rescore pass bought six.

Where It Breaks

The codebooks were trained on last quarter's corpus

A product quantiser is a learned model. Its codebooks minimise reconstruction error over the sample seen at training time, and nothing re-fits them as the corpus changes. Onboard a new product line, switch embedding model versions, or let a multilingual corpus shift language mix, and reconstruction error rises on exactly the new content, which is the content users are asking about. The symptom is a recall regression confined to a subset of queries and invisible in an average. RaBitQ's pitch over PQ is partly this: PQ has no theoretical error guarantee, and its authors note it can fail badly on some real datasets (Gao & Long, SIGMOD 2024). A distribution-free bound degrades predictably; a learned codebook degrades wherever it was not trained.

Boundary loss is not a tail case

The intuition that a query lands "inside" a Voronoi cell alongside its neighbours is a two-dimensional intuition. In 768 dimensions nearly every point is near a boundary, and a query's true neighbours are routinely spread across several cells. Hence IVF's recall curve: nprobe = 1 is not "the right cell", it is one of several the answer might be in. IVFADC keeps code error small by quantising residuals from the centroid rather than raw vectors, but no amount of code fidelity recovers a cell you never opened.

Deletes are tombstones, and tombstones compound

Graph indexes do not really support deletion. hnswlib's mark_deleted omits an element from results but leaves it in the graph, and reusing its slot requires opting in at construction with allow_replace_deleted (hnswlib README). A high-churn corpus accumulates nodes that cost traversal time and contribute nothing, while links that once routed through live nodes now route through dead ones. Recall decays slowly and monotonically; the fix is a rebuild. A corpus with 5% monthly churn is a different operational object than an append-only one. FreshDiskANN exists because the original DiskANN design assumed static data.

Filters break the router, not the scorer

"Nearest neighbours where tenant_id = 42" is not a vector query with a post-processing step. Pre-filtering to the matching subset destroys graph connectivity, because the edges that made traversal work were chosen over the whole corpus; post-filtering the top-\(k\) can return nothing when the predicate is selective. Filtered-DiskANN makes label sets part of edge selection at build time, so traversal can restrict to matching neighbours and still move, reporting order-of-magnitude efficiency gains for filtered queries and thousands of QPS at over 90% recall@10 from SSD (Gollapudi et al., WWW '23, pp. 3406–3416). The cost is a label universe fixed at build time, which rules out ad-hoc predicates. Independent reruns on other datasets report more modest gains than the paper's headline, so treat filtered numbers as workload-specific until measured on your own filter distribution.

[IMAGE: Three panels of the same 2-D point cloud with a selective filter applied, 4% of points highlighted. Panel 1, post-filtering: the top-50 unfiltered neighbours are circled and none are highlighted, so the result is empty. Panel 2, pre-filtering: only highlighted points remain and the graph edges between them are drawn as broken stubs, showing a disconnected subgraph. Panel 3, filtered traversal: edges chosen with label overlap keep the highlighted points connected and a walk reaches the target. Caption: "Filters do not degrade the ranking. They invalidate the structure the router was built on."]

Nobody sizes the rescore budget

k_factor is the most under-tuned parameter in production vector search. At 1 the rescore is decorative: it reorders the top-\(k\) the compressed stage already chose and cannot introduce the candidate it ranked 11^th. At 100 it is a second search. The right value depends on the compressed stage's recall at depth \(k \times \text{k\_factor}\), a far more forgiving quantity than its recall at depth \(k\), and one almost nobody measures. Measure it once and the parameter picks itself.

Recall is measured at build time and never again

Recall requires ground truth, ground truth requires exact search, and exact search is the thing the index exists to avoid. So it gets computed once, on a sampled query set, against a snapshot. Then the corpus grows, the codebooks stay, the tombstones accumulate, and the only recall number anyone can cite comes from the launch document. A nightly job that exact-searches a few hundred sampled live queries against the current corpus is the highest-value observability a vector search system can have.

[IMAGE: Line chart, x-axis months 0 to 12, y-axis recall@10 from 0.80 to 1.00. Three lines: an append-only corpus flat at 0.96; a 5%-monthly-churn corpus decaying to 0.88 with sawtooth recoveries at two rebuild points; a corpus with a distribution shift at month 5 stepping down from 0.96 to 0.90 and staying there. Caption: "Three decay mechanisms, three different fixes, one indistinguishable symptom."]

Alternative Designs

[IMAGE: Decision flowchart three questions deep, matching the rows of the table above. Q1 "fewer than about a million vectors, or very few total queries?" leads to Flat. Q2 "does the whole corpus fit comfortably in RAM?" leads to HNSW,Flat or IVF,Flat depending on whether build cost or query latency dominates. Q3 "can you store full-precision vectors anywhere readable?" leads to IVF,PQ plus refine or DiskANN on a yes, and to SQ8 on a no, with a red annotation on the no branch reading "accept the ceiling". Caption: "The branches are about memory and whether a rescore is available, not about graphs versus cells."]

Every row that compresses carries a rescore requirement; every row that does not carries a memory problem. Two-stage is not an optimisation, it is the price of compression.

How It Is Used in Practice

FAISS's own selection guidance reads as a decision tree over exactly these axes: how many searches will you run, how exact must results be, how important is memory, with the memory answers escalating from Flat through IVF,Flat to OPQ-plus-4-bit-PQ-with-refinement and finally RaBitQ (FAISS wiki). The striking thing is how incidental the routing choice is to that tree: the branches are about memory and exactness, which are quantiser questions.

pgvector makes the opposite bet. It ships HNSW and IVFFlat with no quantiser in the index at all, and offers compression as a type change rather than an index change: halfvec for 2x, or bit with an expression index for \(d/8 + 8\) bytes, in which case the documentation tells you plainly to re-rank with the original vectors (pgvector README). Its conservative defaults reflect a design where index build competes with OLTP traffic for maintenance_work_mem. For a Postgres-resident corpus of a few million rows that is the right trade: no training step, no codebook drift, no second stage.

The sizing habit worth stealing from FAISS is its training-set rule: IVF65536_HNSW32 wants 1.97M to 16.8M training vectors, and larger nlist gets slow enough to warrant GPU or two-level clustering. Train a coarse quantiser on too little data and you get imbalanced cells, which means the nprobe arithmetic in step 4 silently stops holding: one probe might scan 40,000 vectors instead of 3,000. When a latency tail correlates with query region rather than query load, cell imbalance is the first thing to check.

Insights Worth Remembering

1. Routing errors cost time; quantisation errors cost recall you cannot buy back. A router that misses can be funded into correctness. A code that cannot distinguish rank 10 from rank 30 never will, so a flat recall curve under four doublings of nprobe is a diagnosis rather than a plateau to push through.

2. k_factor buys more recall per unit of work than any other parameter, and almost nobody measures it. The compressed stage does not need to rank correctly, only to put the true answers somewhere inside a shortlist. Recall at depth 100 is far weaker a requirement than recall at depth 10, and the gap is free performance.

3. Graph link overhead scales with degree, not dimension, so its significance is entirely relative. 256 bytes per vector is 8% of a 768-dimensional float32 vector and 1,800% of a 14-byte code. The same M = 32 is a rounding error in one index and the dominant cost in another.

4. A coarse quantiser at scale is itself an ANN problem. IVF1048576_HNSW32 is a graph index inside a cell index, which means "graph versus cell" was never the real question.

5. Any published QPS figure without a recall figure is unfalsifiable. The NeurIPS'21 design, fixing throughput and ranking on recall, is the honest inversion, and its 0.71–0.79 band at billion scale is a corrective to vendor charts that end at 0.99.

6. The lifecycle transition with no automatic trigger is the one that pages you. Codebook staleness produces no signal in the serving path, so the nightly sampled exact-search job is the cheapest insurance in the system.

Open Questions

Can a quantiser adapt online without a rebuild? Measured: codebook quality degrades as the corpus distribution shifts, and RaBitQ's distribution-free bound sidesteps the learned-codebook failure mode. Not established: whether incremental codebook refinement can track drift without invalidating already-encoded vectors, which would mean re-encoding history or tolerating a mixed-codebook index. No production system documents doing this today.

What is the right abstraction for filtered search with an open label universe? Filtered-DiskANN shows large gains when labels are known at build time (Gollapudi et al., WWW '23), and independent reruns suggest the gains are workload-dependent. How to serve ad-hoc predicates, especially numeric ranges and join-like conditions, without rebuilding or degenerating to pre- or post-filtering remains open.

Does the two-stage structure survive learned index geometry? Every design here separates picking candidates from scoring them. Whether an end-to-end structure trained jointly against a recall objective beats that separation at scale is untested. The ScaNN result is suggestive in the opposite direction: it improved only the quantisation loss, left routing alone, and reported roughly 2x the QPS at matched accuracy (Guo et al., ICML 2020).

Is one bit per dimension the floor? RaBitQ's follow-up work extends to \(B\) bits per dimension and reports better accuracy-efficiency trade-offs at matched memory. Whether anything below one bit per dimension is useful, via cross-dimension structure rather than per-dimension coding, is not resolved by current published work.

Sources and Further Reading

1. Malkov, Yu. A., & Yashunin, D. A. "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. doi:10.1109/TPAMI.2018.2889473; preprint arXiv:1603.09320.
2. Jégou, H., Douze, M., & Schmid, C. (2011). "Product Quantization for Nearest Neighbor Search." IEEE TPAMI, 33(1), 117–128. doi:10.1109/TPAMI.2010.57.
3. Ge, T., He, K., Ke, Q., & Sun, J. (2013). "Optimized Product Quantization for Approximate Nearest Neighbor Search." CVPR 2013, 2946–2953. doi:10.1109/CVPR.2013.379. Journal version: "Optimized Product Quantization," IEEE TPAMI 36(4), 744–755, 2014.
4. Subramanya, S. J., Devvrit, F., Simhadri, H. V., Krishnawamy, R., & Kadekodi, R. (2019). "DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node." NeurIPS 2019. papers.nips.cc.
5. Fu, C., Xiang, C., Wang, C., & Cai, D. (2019). "Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph." PVLDB, 12(5), 461–474. doi:10.14778/3303753.3303754.
6. Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., & Kumar, S. (2020). "Accelerating Large-Scale Inference with Anisotropic Vector Quantization." ICML 2020, PMLR 119:3887–3896. proceedings.mlr.press.
7. Chen, Q., Zhao, B., Wang, H., Li, M., Liu, C., Li, Z., Yang, M., & Wang, J. (2021). "SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search." NeurIPS 2021. neurips.cc; preprint arXiv:2111.08566.
8. Gollapudi, S., Karia, N., Sivashankar, V., Krishnaswamy, R., Begwani, N., Raz, S., Lin, Y., Zhang, Y., Mahapatro, N., Srinivasan, P., Singh, A., & Simhadri, H. V. (2023). "Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters." WWW '23, 3406–3416. doi:10.1145/3543507.3583552.
9. Gao, J., & Long, C. (2024). "RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search." SIGMOD 2024. doi:10.1145/3654970.
10. Simhadri, H. V., et al. (2022). "Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search." PMLR 176. proceedings.mlr.press.
11. Aumüller, M., Bernhardsson, E., & Faithfull, A. "ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms." Information Systems. doi:10.1016/j.is.2019.02.006. Print issue dated 2020, available online 2019.
12. FAISS wiki, "Guidelines to choose an index." github.com/facebookresearch/faiss.
13. FAISS wiki, "The index factory." github.com/facebookresearch/faiss.
14. pgvector README, parameter defaults and per-type storage. github.com/pgvector/pgvector.
15. hnswlib README, parameter semantics and deletion behaviour. github.com/nmslib/hnswlib.
16. microsoft/DiskANN repository, including FreshDiskANN and Filtered-DiskANN workflows. github.com/microsoft/DiskANN.

Free to read, no ads, no sign-up. If it was useful you can buy me a coffee.