Chapter 15: Approximate Nearest Neighbor Search

00-START-HERE · 01-READING-ROUTES · 14_beyond_plain_text_tables_layout_documents · 16_compression_and_index_economics This chapter explains how to choose and defend an Approximate Nearest Neighbor (ANN) index for Retrieval-Augmented Generation (RAG) under recall, latency, memory, build, and update constraints.

TL;DR

• Exhaustive flat search reads every vector once per unbatched query. High ambient dimension can weaken exact-tree pruning, but it does not make every exact index fail on every dataset.
• HNSW uses sparse upper layers and a dense base graph. HNSW-Flat keeps full vectors; graph links add memory and do not shrink automatically when vectors are quantized.
• IVF routes queries to centroid cells. $\mathrm{nprobe}$ trades routing coverage for list work, while a large $\mathrm{nlist}$ can move the bottleneck to coarse search.
• Classical LSH trades sublinear candidate work for superlinear posting space, plus projection and hashing work. Its radius guarantees do not translate into one universal recall number.
• Directional edges, a useful entry point and a wider search frontier can reduce graph traps. Neither a beam-width setting nor geometric layer occupancy alone proves a query-work bound.
• PQ compresses vectors; disk-resident graphs move bulky records to SSD. Disk capacity, useful read concurrency, IOPS and tail latency must all be budgeted.
• The recall/latency/memory triangle is a Pareto-design heuristic, not an impossibility theorem. Compare matched workloads, measured recall, throughput, rebuild policy and full memory scope.

The story

Imagine a fulfillment warehouse with millions of nearly identical boxes. A customer asks for the box most similar to a photo. Exhaustive flat search means a picker opens every box and compares it with the photo. That works in a small warehouse. In a huge warehouse, the picker spends most of the time walking past bytes of inventory, not thinking. A kd-tree is a rulebook that splits the warehouse by one label at each doorway. The rulebook hopes a single label can prove that an entire wing is irrelevant. In a high-dimensional noise example, distances can cluster tightly and a one-label bound can become too weak to exclude many wings. The picker may then visit much more of the warehouse; this is not an inevitable outcome for every dataset or every combined subtree bound. HNSW is a layered network of warehouse walkways. The sparse top floor has long express walkways. Each lower floor adds shorter local walkways. The picker uses greedy progress on upper floors; at the bottom, a best-first search can keep alternative routes open rather than accepting only one improving move. Its query width is a shortlist of promising candidates. A wider shortlist often improves recall at extra cost, but does not by itself fix how many nodes the picker will expand. IVF is a set of learned warehouse zones. Each centroid is the sign at the center of one zone, and each posting list is the inventory assigned to that sign. The picker first finds nearby signs, then searches only their zones. $\mathrm{nprobe}$ is the number of zone doors opened. One door is fast, but the best box may sit just across the painted boundary. Too many tiny zones create a new problem because reading every sign can cost more than searching the selected shelves. LSH is a collection of yes-or-no stamps placed on every box. One random stamp only weakly distinguishes a matching box from a common box. Concatenating many stamps makes one strict shelf key. Repeating that key across many independent catalogs restores the chance that a true match appears somewhere. Those catalogs consume memory, and short keys flood the picker with false candidates. A graph index is the warehouse walkway plan itself. Connecting each box only to its closest boxes creates dense cul-de-sacs. Directional edge selection reserves walkways that leave a neighborhood. Vamana uses a pruning slack named $\alpha$ to decide which longer walkways survive. Annoy uses several fixed tree maps instead of recoverable walkways. A larger query-time search budget can revisit alternative branches; adding trees is another way to buy recall. DiskANN stores the bulky walkway map and full box records on the SSD. It keeps small PQ labels in Random Access Memory (RAM), so the warehouse can be much larger than memory. Now the cost is storage rounds. Every unnecessary hop becomes a random read. The final choice is a triangle drawn on the warehouse budget sheet. You may demand that the picker almost never misses, returns quickly, and uses little floor space. The triangle records a workload-dependent trade-off, not a proof that all three requirements can never be met. Fix the product constraints, compare feasible operating points, and price the remaining resources before naming an index.

Decoder table

Core mechanics

Mathematical conventions

Unless marked binary, storage is decimal: $1\,\mathrm{GB}=10^9\,\mathrm B$ and $1\,\mathrm{TB}=10^{12}\,\mathrm B$; a $4{,}096$-byte page is $4\,\mathrm{KiB}$. An exact result is relative to the chosen metric, snapshot, filters, tie convention and numerical precision. Flat exhaustive search is one exact algorithm, not the definition of all exact search. For one unbatched full-vector scan, $Ndb/B$ is an ideal streaming-time floor, not measured end-to-end latency; batching may share the vector read. Rounded performance estimates are not tail-latency guarantees. HNSW $\mathrm{ef}$ controls a retained search width, not a hard count of expansions or distance evaluations. Link budgets below include allocated slots under the stated layer convention, not complete process memory. IVF averages assume balanced or representative probed lists. LSH probabilities use unrounded angular collisions and independent random bits/tables; candidate expectations are not fixed counts. Round required machines, bits and tables upward. Empirical study findings remain reported inputs, not consequences proved by the arithmetic.

15.1 Why exact search dies: the curse of dimensionality

• What flat exact scan does: Score every eligible vector and return the true top $k$ under the specified metric and tie convention. Exact tree algorithms may instead prune with valid bounds.
• Why it exists: No learned partition or approximate traversal is needed. The vector store and filters still need correct updates; numerical precision and top-$k$ selection remain implementation choices.
• Work: A dense fp32 dot-product scan reads $4Nd$ vector bytes and uses approximately $2Nd$ FLOPs, counting a multiply and add separately. More exactly, summing $d$ products takes $2d-1$ scalar operations per vector before scoring/selection overhead.
• Arithmetic intensity: Approximately $0.5\,\mathrm{FLOP/B}$ for vector traffic alone. Under low arithmetic intensity and unbatched streaming, bandwidth is often the bottleneck.
• Ideal roofline: With sustained shared bandwidth $B$ and arithmetic rate $F$, $t\gtrsim\max(4Nd/B,2Nd/F)$. Selection, query reads, normalization, filtering and scheduling add work.
• Throughput scope: $\mathrm{QPS}\le B/(4Nd)$ is a vector-bandwidth ceiling only when each query requires its own full scan; batching and reuse can amortize the vector read. For $N=10^7,d=768,B=50\,\mathrm{GB/s}$, the vector payload is exactly $30.72\,\mathrm{GB}$. The ideal unbatched streaming estimate is $0.6144\,\mathrm s=614.4\,\mathrm{ms}$, with ceiling $1.627604\,\mathrm{QPS}$. Calling this a floor assumes the algorithm really reads all those bytes through that bandwidth bottleneck; exactness alone does not require every exact algorithm to do so.
• What a kd-tree does: Partition coordinates, descend to candidate leaves, and use the current best full-space radius to test unexplored regions.
• Simple sibling test: At a split $x_i=s$, $\lvert q_i-s\rvert\gt r$ is sufficient to exclude the opposite half-space. A subtree’s full bounding-box lower bound can combine several coordinate gaps and prune even when this one-axis test fails.
• Failure mode: For some high-dimensional distributions, these bounds exclude little, so traversal approaches a scan with extra pointer and bookkeeping costs.
• Limit: Expected near-logarithmic behavior requires favorable geometry and balance; it is not a universal exact-query guarantee. For two independent vectors $X,Y\sim\mathcal N(0,I_d)$, let $D=\lVert X-Y\rVert$. Then $D^2/2\sim\chi_d^2$, so $\mathbb E[D^2]=2d$ and $\mathop{\mathrm{Var}}\nolimits(D^2)=8d$. The delta method gives $\mathbb E[D]\approx\sqrt{2d}$, $\mathop{\mathrm{sd}}\nolimits(D)\approx1$ and $\mathrm{CV}\approx1/\sqrt{2d}$ for large $d$. Exact moments are

The exact CVs are approximately $36.300\%$, $8.85595\%$ and $2.55197\%$ at $d\in\{4,\,64,\,768\}$; the first-order $35.355\%$ value at $d=4$ is not exact. At $d=768$, the unconditional pairwise mean is $39.17908$ with standard deviation $0.99984$. Distances to many points share the same query, so they are not independent unconditionally. Conditional on a fixed query $q$, $\lVert X-q\rVert^2\sim\chi_d^{\prime2}(\lVert q\rVert^2)$, with mean $d+\lVert q\rVert^2$ and variance $2d+4\lVert q\rVert^2$. At $\lVert q\rVert^2=d=768$, the local delta-method distance spread is $\sqrt3/2\approx0.86603$, not $1$. For $N=10^7$, the conditional distance quantiles with one-tail probability $1/N$ are approximately $34.72881$ and $43.72841$, ratio $1.259139$. These are quantile markers, not expected extrema or hard bounds. They replace the inconsistent $33.5/44.9$ independent-pair extreme heuristic. The conditional CDF is evaluated through its Poisson mixture of central chi-square CDFs. A one-coordinate distance to a median split at zero has $\mathbb E\lvert Z\rvert=\sqrt{2/\pi}\approx0.797885$ for $Z\sim\mathcal N(0,1)$; a difference between two independent point coordinates instead has expected absolute value $2/\sqrt\pi\approx1.128379$. Actual tree split gaps depend on the construction.

• Geometric warning, not a no-pruning proof: Coordinate-plane gaps of order $1$ can be much smaller than nearest-neighbor radii of order $\sqrt d$ in this noise model. This motivates weak pruning; it does not show every sibling survives every bounding-box test.
• Depth: A roughly balanced binary tree with $10^7$ singleton leaves has a depth scale $\lceil\log_2 10^7\rceil=24$. Leaf size and imbalance alter it.
• Coordinates: One path has at most $24$ split tests, potentially repeated on the same coordinate; it need not constrain $24$ distinct axes. Thus $744$ is a lower bound on untouched axes only in this limited path-count comparison, not a characterization of the entire search.
• Exponential grid: A complete binary decision tree that branches once on every one of $768$ coordinates has $2^{768}$ leaves. Exact search does not require building that grid. Ball trees, $R$-trees and related schemes can suffer similarly, but behavior depends on the dataset, intrinsic structure, metric and bounds. The cited $1998$ experiment found sequential scan faster than the tested partitioning indexes above roughly ten dimensions; it is not a modern hardware-independent cutoff. The cited $1999$ distance-concentration result needs its distributional conditions; convergence of a farthest/nearest ratio does not apply to every learned corpus or every joint scaling of $N$ and $d$. Approximation offers query-dependent graph, cell or hash candidates rather than an exact pruning certificate.
• Geometry: Random high-dimensional vectors can have weak distance contrast; exact neighbor ranks still exist, and query-dependent algorithms may exploit structure. Concentration alone does not prove all ANN methods useless.
• Learned representations: Semantic training may produce navigable clusters or lower effective dimension, but this is a hypothesis to inspect, not guaranteed by the embedding width.
• Evidence: Measured $0.95$ recall while scoring $0.1\%$ of a corpus demonstrates a useful operating point for that graph, dataset and queries. It does not logically refute every independent-noise model or prove a particular manifold dimension.
• Terminology: This section uses the curse of dimensionality for distance concentration and weak pruning, not as a derivation of all sample-complexity or shell-volume phenomena. Worked CPU scan. Use $10^7$ fp32 vectors of width $768$, a $20\,\mathrm{ms}$ search allowance within a $200\,\mathrm{ms}$ pipeline $p_{95}$ target, and $500$ QPS. The vector-read floor is $614.4\,\mathrm{ms}$; dot-product work is $15.36\times10^9$ FLOPs. A hypothetical $3\,\mathrm{GHz}$ core at $32$ fp32 FLOPs/cycle offers $96\times10^9\,\mathrm{FLOP/s}$, or $160\,\mathrm{ms}$ compute time. The ratio is $3.84$, supporting the bandwidth bottleneck under these assumptions, not an independent timing measurement. The floors are $30.72$ and $8$ times the search allowance. Aggregate unbatched bandwidth at $500$ QPS needs $\lceil500(0.6144)\rceil=308$ socket-equivalents, not $313$; rounding QPS before inversion caused the discrepancy. Independent parallel queries do not by themselves reduce one query’s latency; query sharding adds its own work. Worked GPU batch. On the stated A100 $80$GB example, published $2{,}039\,\mathrm{GB/s}$ gives $15.0662\,\mathrm{ms}$ for one vector read. Batch $16$ uses $245.76\times10^9$ FLOPs; at $19.5\times10^{12}\,\mathrm{FLOP/s}$ its compute floor is $12.6031\,\mathrm{ms}$. An ideal fully shared matrix read therefore has roofline service time at least $15.0662\,\mathrm{ms}$ and throughput ceiling about $1{,}062$ QPS. This is not measured service or $p_{95}$ latency. With regular arrivals at $500$ QPS and full batches only, the first query waits $30\,\mathrm{ms}$ to fill a batch and mean fill wait is $15\,\mathrm{ms}$; dynamic batching must budget that separately. At $10^9$ vectors, payload is $3.072\,\mathrm{TB}$. Reading it within $20\,\mathrm{ms}$ requires $153.6\,\mathrm{TB/s}$, at least $76$ such peak-bandwidth accelerators before capacity, transfer, selection and interconnect costs—not an implementable latency guarantee. Illustrative graph work. With $M=32,M_0=64$, assume $128$ base-node expansions and no repeated candidate distances: $128(64)=8{,}192$ evaluations, $0.08192\%$ of the corpus. The choice $\mathrm{ef}_{\mathrm{search}}=128$ does not guarantee this expansion count. Vector reads would be $25.165824\,\mathrm{MB}$, $1{,}220.703$ times less than flat, with $0.5033\,\mathrm{ms}$ streaming time at $50\,\mathrm{GB/s}$ before graph reads and scattered-access effects. Base-layer link slots use $256\,\mathrm{B/vector}$, $2.56\,\mathrm{GB}$ or $8.333\%$ of vector bytes; upper layers and other structures are additional. Actual recall, unique evaluations and traversal time must be measured. Sanity check and operations. SIFT1M at $d=128$ has $512\,\mathrm{MB}$ fp32 payload and a $10.24\,\mathrm{ms}$ scan floor, $97.65625$ unbatched QPS at the same shared bandwidth. The cited HNSW benchmark’s two-to-three-order throughput gain at recall $0.9$ is reported evidence under its own setup, not a consequence of the $1{,}220$ work ratio in the different example. For an otherwise idle unbatched scan, $\lfloor(50\times10^9)(0.020)/(4\times768)\rfloor=325{,}520$ vectors is a bandwidth-only $20\,\mathrm{ms}$ threshold, not a universal flat/ANN crossover. High QPS, selection and measured tail latency can lower it; batching or different hardware can raise it. Halving $d$ or component bytes halves this vector-read term, not every index cost. If exactness is required, use a method that certifies it rather than assuming high measured recall is enough. Brute-force $1{,}000$ representative queries and inspect $d_{100}/d_1$ under a defined distance with $d_1\gt 0$. Values such as $1.5$ or near $1$ are diagnostics, not universal quality thresholds or impossibility proofs; embeddings and cosine-to-distance conventions matter. Use random vectors only for an explicitly labeled noise stress test. Tenant prefiltering can make flat search feasible, but validate filtered ground truth, per-tenant load, query routing and shared-capacity costs.

15.2 From skip lists to HNSW

• What a skip list is: A sorted linked list with progressively sparser upper levels.
• Why it exists: Upper pointers skip long stretches while preserving a local, certain halting test.
• Search rule: Advance while the next key is below the target, then descend when it is not.
• Example: Searching for 17 advances from the head to 7 on level 2, descends before 29, advances 7 to 16 on level 1, descends again, then reaches 17 on level 0.
• Example cost: Three advances and two descents replace scanning nine values. With independent promotion probability $0\lt p\lt 1$, expected occupancy of level $\ell$ is $np^\ell$. The characteristic highest-level scale is $L(n)=\log_{1/p}n$, not a deterministic maximum. For example, $\Pr(L_{\max}\lt j)=(1-p^j)^n$. Standard skip-list analyses bound expected search comparisons by expressions of the form $L(n)/p+1/(1-p)$ under their counting convention. At $p=1/2,n=10^7$, $L(n)\approx23.2535$ and this expression is $48.5070$, about $49$ comparisons or $2.06\times10^5$ fewer than a ten-million-step linear lookup. Constants, sentinels and equality tests affect the exact count. A total order makes the local stopping test valid; it does not make storage or updates free.
• Losing alternative: Sort vectors by distance to one pivot.
• Why it fails: Triangle inequality gives only $\lvert d(x,p) - d(y,p)\rvert \le d(x,y)$, which is a lower bound.
• Failure: Equal pivot distance says nothing about pairwise distance.
• High-dimensional effect: Distance concentration places most points in a narrow band around the pivot. HNSW replaces ordered-list links with stored geometric neighbors. Upper levels usually use greedy descent; the base search keeps candidates and a retained best set, so it may explore alternatives after a local greedy optimum. Its upper-layer stopping test certifies only a local result, not the global nearest vector. Under the stated layer convention,

Thus $\mathbb E[N_j]=nM^{-j}$. At $M=16,n=10^7$, the characteristic top-index scale is $\log_{16}10^7\approx5.81337$, with expected occupancies $625{,}000$ at layer $1$, $9.53674$ at layer $5$, and $0.59605$ at layer $6$. The number of occupied layers is random and includes layer $0$; $5.8$ is not literally a six-layer guarantee. Geometric occupancy alone does not prove logarithmic graph-search work.

• Nearest-only links: They can waste degree within one cluster and even form disconnected components, but this is a possible failure, not a theorem for every $k$-NN graph.
• Diversity heuristic: Process candidate neighbors by distance from a new point $p$. One common rule accepts $e$ when $d(p,e)\lt d(e,r)$ for every already accepted $r$, subject to tie and degree policies.
• Purpose and limit: This favors additional directions and longer cross-cluster links. It is not a global connectivity or recall certificate, especially with an approximate candidate set and capped degree. Flat NSW combines links on one level. HNSW’s hierarchy often improves entry and observed scaling; the cited polylogarithmic/logarithmic behaviors should be treated as model- or benchmark-scoped, not distribution-free worst-case bounds. Random promotion allows local insertion without renumbering a rigid every-other-node schedule. Deterministic balanced skip structures can also support local updates; a global rebuild is not inherent to determinism. Physical graph deletion may require inbound-neighbor repair, while logical tombstones can defer it. Illustrative query budget. Let $M=16,M_0=32$, and separately assume five upper levels with two expanded nodes each and $64$ expanded base nodes. This gives $5(2)(16)+64(32)=2{,}208$ neighbor-distance evaluations if none are reused, a $4{,}528.986$ work reduction versus $10^7$. It is not a bound implied by $\mathrm{ef}_{\mathrm{search}}=64$. Reading a fresh $3{,}072$-byte vector for each evaluation costs $6{,}782{,}976$ bytes; expanded adjacency slots add $[5(2)(16)+64(32)]4=8{,}832$ bytes, total $6.791808\,\mathrm{MB}$. At an assumed effective scattered-read rate of $10\,\mathrm{GB/s}$, this component is $0.67918\,\mathrm{ms}$. The older $7.1\,\mathrm{MB}$ model charged an entire base neighbor list per evaluated candidate, rather than per expanded node. Neither model establishes observed latency or recall; metadata, caches and access dependencies matter. Scoped link memory. With four-byte IDs, expected allocated link slots contribute

At $M=16$, this is $132.266667\,\mathrm{B/vector}$: $128$ at the base and $4.266667$ above. Ten million fp32 vectors plus these slots use $32.042667\,\mathrm{GB}$, $4.30556\%$ over vector payload. The documented rule $4d+8M=3{,}200$ omits the upper-slot term; its scoped undercount is about $0.1332\%$, not a complete allocation audit. Counts, pointers, alignment, external IDs, visited sets, locks and payload remain additional. With $64$-byte PQ codes, the same expected slots give $196.266667\,\mathrm{B/vector}$ and $1.962667\,\mathrm{GB}$; links occupy $67.3913\%$. The base-only shortcut is $192$ bytes and $1.92\,\mathrm{GB}$, and must be labeled as such. Graph links are not mathematically incompressible; they simply do not shrink automatically with the vector codes. Build and tuning. Assuming $200$ expansions of $32$ candidates per insertion would give $6.4\times10^{10}$ evaluations over $10^7$ inserts, $2.89855\times10^7$ of the illustrative $2{,}208$-evaluation queries. $\mathrm{ef}_{\mathrm{construction}}=200$ is not a hard per-insert evaluation limit, and this is not a build-time bound. Start with a measured $M=16$ baseline and sweep query $\mathrm{ef}$; it changes both recall and work and is reversible. If expansions happened to double from $64$ to $128$, the base term would double from $2{,}048$ to $4{,}096$—the parameter alone does not promise that. Increase $M$ or build width when the measured runtime curve misses target. Base-slot bytes double from $128$ to $256$ at $M=32$; including expected upper slots, ten million vectors need $1.278624\,\mathrm{GB}$ extra links. Choose query width large enough for $k$ and the implementation’s constraints. Build width $200$ versus query width $64$ is an example, not a requirement that build width always exceed every later query width. Monitor tombstone effects and rebuild or repair according to measured behavior; deleted nodes may remain traversable without occupying result slots. At $500$ million vectors, these expected-slot floors are $1.602133\,\mathrm{TB}$ for HNSW-Flat and $98.1333\,\mathrm{GB}$ for HNSW with $64$-byte codes, including $66.1333\,\mathrm{GB}$ of links. IVF-PQ with $64$ code bytes and an $8$-byte ID has $36\,\mathrm{GB}$ of entries before fixed terms. If its measured recall/probe curve fails the target, consider more memory, additional machines or disk-resident search; no fixed corpus-size threshold makes one family universally best.

15.3 IVF: coarse quantizers, centroids, Voronoi cells

• IVF: Fit representative centroids, assign each vector to a cell, then score selected posting lists. Storage format and routing are separate choices.
• Why: Candidate scans may be much smaller and more batch-friendly than a full scan.
• Counterexample scope: A grid with two bins on each of $768$ axes has $2^{768}$ cells. This is one impractical grid construction, not a requirement of all data-independent routing.
• Failure modes: Poorly matched boundaries or an uneven distribution can overload lists or miss nearby points. Learned partitions can have these problems too. For Euclidean IVF, fit $K=\mathrm{nlist}$ centroids and set $q_c(x)\in\arg\min_i\lVert x-c_i\rVert$, with a tie rule. Cell membership satisfies

For distinct centroids the separating plane is their perpendicular bisector. A Voronoi cell is an intersection of half-spaces: a convex polyhedron, possibly unbounded, and a polytope only if bounded. Tied boundaries need assignment conventions. Inner-product or other routing choices need their own geometry. The inverted file maps centroid IDs to posting lists, analogous to a text index mapping terms to postings. With flat full-vector centroid comparisons and balanced representative probed lists, a continuous distance-count proxy is

Here $T'(K)=1-wN/K^2$ and $T''(K)=2wN/K^3\gt 0$. The minimum assumes fixed $w$, equal-cost centroid and candidate comparisons, and feasible integer $1\le w\le K\le N$. Recall changes with $K,w$ and is not optimized by this derivative. At $w=1$, $T(K_\star)=2\sqrt N$, giving work reduction $\sqrt N/2\approx1{,}581.139$ at $N=10^7$. PQ scoring, indexed centroids, imbalanced lists and hardware change the model.

• Boundary miss: A true neighbor may be in a different cell, especially near a bisector. It is not inevitable for every boundary-near query.
• Probe behavior: Querying multiple nearby centroids can recover missed cells, but the true neighbor’s cell need not be among a small chosen set.
• Geometry limit: A cell can have at most $K-1$ other-cell face neighbors. “Most volume lies near a face” requires a bounded region, distribution and boundary thickness; unbounded Voronoi cells have no uniform finite-volume distribution. For a cube of side $a$, a boundary band of thickness $\varepsilon\lt a/2$ occupies fraction $1-(1-2\varepsilon/a)^d$—an illustrative concentration model, not a theorem about every learned cell.
• Cost: Raising $\mathrm{nprobe}$ scans more selected lists without retraining; their actual total length, not just their count, determines work. At $N=10^7,d=768$, the flat vector-read floor is $30.72\,\mathrm{GB}$ and $614.4\,\mathrm{ms}$ at $50\,\mathrm{GB/s}$. Under the balanced-list/full-vector proxy:
• $K=4{,}096,w=1$: mean list length $2{,}441.40625$, total $6{,}537.40625$ equivalent distances, $20.082912\,\mathrm{MB}$ and $0.401658\,\mathrm{ms}$ of vector streaming. Reduction is $1{,}529.659$; routing loss remains.
• $K=4{,}096,w=32$: list work $78{,}125$, total $82{,}221$, $0.82221\%$ of $N$, $252.582912\,\mathrm{MB}$ and $5.051658\,\mathrm{ms}$. Flat reduction is $121.6234$, with $4.9817\%$ of distances in the coarse scan.
• $K=65{,}536,w=32$: mean list length $152.587890625$, list work $4{,}882.8125$, total $70{,}418.8125$. This is $14.3542\%$ below $82{,}221$, not a $16$-fold total-work win; coarse comparisons are $93.0660\%$ of the proxy.
• If a centroid HNSW search is separately budgeted at $1{,}000$ comparisons, the last total becomes $5{,}882.8125$, a $13.9765$ comparison-count reduction versus the $4{,}096$-cell, $32$-probe case. That centroid approximation can itself miss useful cells; the number is neither guaranteed recall nor measured speedup. Fractional list sizes are averages, not actual per-query counts. Never multiply rounded $2{,}441$ or $153$ and present the unrounded total as an exact product. With flat coarse search, $\sqrt{32\times10^7}\approx17{,}888.544$ is the continuous cost optimum; nearby integers need comparison. Reported library guidance such as $65{,}536$ cells in a given scale band or $4\sqrt N$ to $16\sqrt N$ in another band is empirical guidance. Indexed centroids can make larger $K$ viable, but do not alone prove those choices optimal.
• Training: A learned IVF coarse quantizer must be trained before ordinary population. Distribution shift can change list balance and recall; stale centroids do not inevitably reduce every metric.
• Implementation rules: The cited $39$ points per centroid is a warning threshold, not a mathematical training lower bound or recall guarantee. A default maximum of $256$ training points per centroid is a configurable sampling cap, not a target that must exceed the corpus size.
• Numbers: At $65{,}536$ centroids, these settings correspond to $2{,}555{,}904$ and $16{,}777{,}216$ training points. For a $10^7$-vector corpus, the latter is above the available distinct points; do not invent extra samples to satisfy it. Use $K\approx4\sqrt N$ as a starting heuristic, not a fixed optimum. Measure coarse-stage share before switching to an indexed coarse quantizer; $16{,}384$ centroids is a workload-specific suggestion, not a universal cutoff. Tune integer $1\le\mathrm{nprobe}\le\mathrm{nlist}$ against exact-neighbor recall. $\mathrm{nprobe}/\mathrm{nlist}$ is a balanced-list scan fraction, not recall and not an exact cost fraction for imbalanced lists. Without task labels, exact search on the same frozen, filtered snapshot can still supply ANN ground truth. A starting $\max(1,\lceil K/128\rceil)$ and $1{,}000$ representative queries is an audit heuristic; sweep the parameter and report uncertainty, not an automatic bisection guarantee under noisy estimates. Service tiers such as probes $8$ and $64$ should satisfy their own latency/recall targets. Inspect selected-list lengths and load: $p_{99}/p_{50}=10$ is not unique evidence of imbalance; queuing, cache misses and other effects can cause it. IVFFlat adds IDs and centroids but keeps full vectors. At $K=4{,}096,N=10^7,d=768$, $8$-byte IDs plus fp32 centroids add $92.582912\,\mathrm{MB}$, about $0.30138\%$ of vector payload. This scope excludes list, allocator and external metadata overhead. At $200$ million vectors, fp32 payload is $614.4\,\mathrm{GB}$. Standard HNSW expected slots at $M=32$ add approximately $52.025806\,\mathrm{GB}$, not the $76.8\,\mathrm{GB}$ obtained by assuming $3M$ links at every node. With $65{,}536$ centroids, IVFFlat IDs and centroids add $1.801327\,\mathrm{GB}$. A $96$-byte PQ code reduces vector payload to $19.2\,\mathrm{GB}$, a $32$-fold vector-only reduction; IDs, codebooks, centroids and refine vectors remain additional. Quantization often dominates the memory choice at this scale, but no architecture wins independently of recall, rebuild and serving costs.

15.4 LSH and hash-collision retrieval

• Ordinary hashing: Expected bucket lookup can be constant time under a load model, but avalanche-style fingerprints do not preserve approximate vector similarity.
• LSH: A near/far collision guarantee supports candidate retrieval without fitting a coarse partition. The general definition does not require collision to be globally monotone between the design radii; the hyperplane family below is monotone in angle.
• Trade-off: Independent tables can consume superlinear posting space and produce many candidates. Actual competitiveness depends on the metric, data, projection computation and implementation, not only an exponent. A family is $(R,cR,p_1,p_2)$-sensitive for $R\gt 0,c\gt 1,0\lt p_2\lt p_1\lt 1$ if pairs at distance at most $R$ collide with probability at least $p_1$, while pairs at distance at least $cR$ collide with probability at most $p_2$. The guarantee leaves the intermediate annulus unspecified. For random-hyperplane cosine hashing, use nonzero normalized vectors and $r\sim\mathcal N(0,I_d)$:

At cosine $0.8$, $\theta\approx0.643501109$ and $p_1\approx0.7951672353$; at cosine $0.3$, $\theta\approx1.266103673$ and $p_2\approx0.5969866840$. The per-bit margin is approximately $0.1981805513$. Keep these unrounded probabilities for all powers and table counts.

• What AND amplification does: Concatenate $b$ independent bits into one table key.
• Probability: One-table collision becomes $p^b$.
• Why it helps: The smaller $p_2$ shrinks faster than $p_1$.
• What OR amplification does: Build $L$ independent tables and union their candidates.
• Probability: Retrieval becomes $1 - (1 - p^b)^L$.
• Why it helps: It restores near-neighbor recall after the strict key lowers all collisions.
• Cost: Every table stores another full set of corpus identifiers. Classical asymptotic construction. For a real-valued algebraic code length $b_0=\log_{1/p_2}N$, $Np_2^{b_0}=1$. Define $\rho=\ln(1/p_1)/\ln(1/p_2)$, so $p_1^{b_0}=N^{-\rho}$. At $L\approx N^\rho$, success for a qualifying near point approaches $1-e^{-1}\approx0.632121$. A real index needs integer $b,L$; $b=\lceil b_0\rceil$ keeps $Np_2^b\le1$, and $L=\lceil p_1^{-b}\rceil$ gives at least the corresponding constant-success scale. Target success $1-\varepsilon$ instead needs

The usual candidate/probe scaling is $O(N^\rho)$ with $O(N^{1+\rho})$ posting entries under the model; projection and hashing add work such as $O(Lbd)$ for separately computed dense hyperplanes, often suppressed with dimension/log factors or preprocessing assumptions. The construction solves an approximate near-neighbor radius problem, not a universal top-$k$ recall guarantee. Its query-work bound uses the model's candidate limits or early acceptance of a qualifying point. Exhaustively unioning and reranking buckets for top-$k$ is a different procedure: many points in the intermediate-distance annulus or overloaded buckets can produce linear-size candidate sets even though the far-point collision bound holds. Duplicates, short keys and metric choice also affect actual work. Integer classical example. With $N=10^7$ and the unrounded cosine-derived $p_1,p_2$, $\rho\approx0.444311671$, $b_0\approx31.2450683$, hence choose $b=32$, not $31$. Taking $L=1{,}533$ gives qualifying-point success about $0.6324214$. If every background point has cosine $0.3$, expected far candidates per table are $0.6774365$ and the deduplicated expected far union is approximately $1{,}038.456$; these are expectations, not guaranteed counts. Projection uses $49{,}056$ hyperplane dots or $37{,}675{,}008$ MACs at width $768$. Far-candidate reranking adds about $797{,}534$ MACs, plus any qualifying-point and bookkeeping work. Against $7.68\times10^9$ brute-force MACs, this arithmetic-only ratio is about $199.62$, not a measured speedup. Posting IDs alone require $1{,}533(10^7)(8)=122.64\,\mathrm{GB}$, before buckets, keys and $30.72\,\mathrm{GB}$ of vectors if retained for exact reranking. Rounding the old exponent and using $31$ bits produced internally inconsistent table, candidate and memory totals. Short-key, high-success example. Set $b=16$. At cosine $0.8$, $p_1^{16}\approx0.0255467482$ and the minimum independent-table count for $99\%$ pair retrieval is $178$. The exact model gives $0.990012435$ near retrieval and $0.045278093$ retrieval at cosine $0.3$, not the figure’s former $0.994/0.049$. At cosine $0.75$, retrieval is $0.935173546$; the decrease is $5.4839$ percentage points from the $0.8$ case. Far-candidate expectation is $452{,}780.930$ if all $10^7$ background points have cosine $0.3$. Background cosine $0.1$ gives $72{,}764.328$, or $0.727643\%$, instead. For heterogeneous background items, expected candidates are the sum of their individual retrieval probabilities; far-radius collision bounds yield an upper bound, not equality. Independent dense projections cost $2{,}187{,}264$ MACs here, and the cosine-$0.3$ expected rerank costs $347{,}735{,}754$ MACs. The combined arithmetic-only ratio versus flat is $21.9477$. IDs occupy $14.24\,\mathrm{GB}$. Storing an optional redundant two-byte key per posting adds $3.56\,\mathrm{GB}$, yielding $17.8\,\mathrm{GB}$ for that layout, not mandatory LSH space; bucket-key layouts differ. Full rerank vectors and table metadata remain additional. The $1.322667\,\mathrm{GB}$ HNSW $M=16$ link-slot floor is about $13.46$ times smaller than that optional posting-plus-key budget, but this is neither a whole-index comparison nor a matched-recall benchmark. A beam width is not a measured HNSW candidate count. Theory scope. The cited Euclidean LSH exponents $1/c^2$ and data-dependent $1/(2c^2-1)$ are asymptotic theoretical results under their respective models and resource assumptions. On unit vectors, $R^2=2(1-0.8)=0.4$ and $(cR)^2=2(1-0.3)=1.4$, giving $c^2=3.5$, exponents $2/7\approx0.285714$ and $1/6\approx0.166667$. The expression $(10^7)^{2/7}=100$ is an exponent illustration, not a finite-instance prediction of $100$ candidates or a proof that this hyperplane index is a fixed factor from an attainable optimum. The cited graph-versus-hash frontier is a reported benchmark, not a theorem over all datasets. Practice. Default to measured graph/IVF baselines for vector ANN; LSH remains useful for some updates, similarity joins and deduplication. Choose $b$ from a stated far-collision model, then price the required $L$ at the desired success radius. Instrument deduplicated candidates and all projection work, not recall alone. The cited web-scale SimHash setting uses $64$ bits and Hamming distance at most $3$ over more than $8$ billion pages; it is not an infallible duplicate definition. Use MinHash when set/Jaccard overlap is the intended similarity. State table count and bucket work for multi-probe variants. Inserts and removals touch up to $L$ tables, so they are local to postings but not constant work independent of $L$. A hot-slice LSH/cold-graph hybrid is a workload option, not a conclusion from an unmatched $14$-times memory comparison.

15.5 Graph indexes: RNG, Vamana/DiskANN, Annoy

A proximity-graph index stores vector nodes and selected edges. Queries may use greedy upper-level routing, best-first search or wider beams; not every graph search is a pure greedy walk. Candidate generation, edge selection, entry policy and stopping rules jointly determine quality and cost.

• Nearest-only rule: It can trap degree within one cluster, leave disconnected components or create a local greedy optimum; it does not necessarily do so on every corpus.
• Directional selection: Reserve some degree for distinct directions and possible cluster crossings, rather than minimizing every edge’s length.
• Limit: Degree diversity is a useful construction principle, not by itself a certificate of global reachability or exact search. Cone record-minimum toy. Distinguish the randomized cone construction here from the relative-neighborhood-inspired pruning used below. Suppose a fixed collection of $C$ cones covers directions around a node. Within one cone, randomly permute $m$ distinct candidate distances and retain every new prefix minimum. Position $i$ is a record with probability $1/i$, hence $\mathbb E[\#\mathrm{records}]=H_m=\sum_{i=1}^m1/i=\ln m+\gamma+O(1/m)$. At fixed cone count, expected edge storage is $O(CN\log N)$; $C$ can grow steeply with dimension and narrower cone width. The retained set need not contain only the final nearest point. Enumerating every point pair already requires $O(N^2)$ distance comparisons and approximately $O(N^2d)$ coordinate work, before cone tests. Record-count arithmetic alone does not establish logarithmic query hops; any such cited theorem needs its geometric and construction assumptions. Vamana pruning. At node $p$, process a candidate set by choosing the nearest surviving $p^*$, adding it to neighbors, and deleting candidates $q$ satisfying

At $\alpha=1$, this is a relative-neighborhood-inspired occlusion test closely related to the HNSW diversity heuristic. The algorithms are not identical, and testing only retained candidates need not reproduce the full mathematical relative neighborhood graph. Increasing $\alpha$ makes this deletion test harder for a fixed retained point; the final capped greedy construction is not necessarily nested as a whole, because earlier choices can change. More candidates can survive and use the degree budget, often including useful longer edges. Conditional shrinkage proof. Assume the target $q$ is itself a dataset point, every other point was available to each node’s pruning step, and no candidate was left uncovered by a degree-cap stop. Then either $p\to q$ is retained or $q$ was removed by some retained $p^*$ satisfying $d(p^*,q)\le d(p,q)/\alpha$. For $\alpha\gt 1$, a greedy choice at least as good as that witness yields $d_h\le d_0\alpha^{-h}$. If $d_{\min}\gt 0$ is the minimum interpoint separation and $\Delta=d_0/d_{\min}\ge1$, the target must be reached by

since one further strictly sub-$d_{\min}$ distance can only be zero. At $\Delta=10^4$, the logarithmic scales are $50.5170$ for $\alpha=1.2$ and $22.7155$ for $\alpha=1.5$, giving conservative integer bounds $51$ and $23$ in this ideal covered-point setting. At $\alpha=1$, this multiplicative-shrinkage argument provides no logarithmic bound. It does not prove an arbitrary external query, approximate candidate construction, capped degree or real DiskANN walk obeys those hop counts. On disk, actual dependent I/O rounds—not this ideal formula alone—control latency.

• Annoy: A forest of random-projection trees, often built from approximate two-means/split procedures. A perpendicular-bisector split between two representatives is a simplified model, not every implementation detail.
• Query: Search can keep a priority queue of alternative branches and inspect more leaves within one tree. It is false that a wrong descent can only be repaired by searching another tree.
• Knobs: Tree count adds build work and storage; query-time $\mathrm{search\_k}$ or an equivalent visited-node budget can also buy recall without rebuilding.
• Use case: A static read-only memory-mapped forest may be operationally useful. Loading lazily does not imply a cold first query has zero page-fault or storage cost. In the illustrated graph, greedy search takes $E\,(63.6)\to P_5\,(50.4)\to P_1\,(38.6)\to P_4\,(22.4)$, with numbers denoting distance to $Q$. $P_4$’s back edge to $P_1$ is uphill, so strict greedy progress stops. The true nearest point $P_9$ has distance $5.66$ and is reached through $P_6\,(36.9)\to P_7\,(30.5)\to P_8\,(20.0)\to P_9$. At the branch, $P_4$ beats $P_6$ by $14.5$. A best-first retained set of width $2$, with the shown edges and standard visited-node handling, keeps the alternate branch and expands $P_6,P_7,P_8,P_9$ after $P_4$. This demonstrates one recovery, not a proof that width $2$ always escapes a trap.
• Guarantee limits: Approximate candidates, a degree cap that leaves targets uncovered, external queries, ties and update policies can each invalidate the ideal shrinkage proof.
• Mitigation: Best-first candidates, wider exploration and better entry policies can help empirically, but none automatically restores the missing theorem.
• Entry examples: A sample tree, medoid, multiple entries or a hierarchy may reduce entry cost; choose by the measured workload rather than assuming one is always best. Resident graph floor. At $N=100$ million, $d=768$ and fp32, vectors use $307.2\,\mathrm{GB}$. Exactly $64$ four-byte outgoing slots per node add $25.6\,\mathrm{GB}$, total $332.8\,\mathrm{GB}$ before degree counters, headers, locks, payload and headroom. Dividing by $64\,\mathrm{GB}$ gives $5.2$, so at least $6$ such memory allocations would be needed under ideal sharding; this is not a complete machine or latency plan. Forest illustration. Suppose a simplified binary forest has exactly $\lceil10^8/64\rceil$ leaves per tree and a full $768$-float normal per internal node. It has $1{,}562{,}499$ internal nodes, approximately $4.8\,\mathrm{GB}$ of normals per tree or $240\,\mathrm{GB}$ for $50$ trees. Those normals alone are $0.78125$ times the vector payload; normals plus one shared vector payload are about $1.78125$ times it. The old claim that the $240\,\mathrm{GB}$ forest alone was $1.8$ times $307.2\,\mathrm{GB}$ conflated the two. Actual Annoy leaf capacity, node layout, representative construction and mapping overhead differ; measure its file and resident working set. Disk record illustration. $96$-byte PQ codes use $9.6\,\mathrm{GB}$ RAM at $100$ million points, $15\%$ of a decimal $64\,\mathrm{GB}$ machine before cache and other structures. Assume full vectors, four-byte neighbor IDs and a four-byte degree count are stored in separately aligned $4\,\mathrm{KiB}$ node records. Then

At $R=64$ a record is $3{,}332$ bytes, leaving $764$ bytes. At $R=255$ it exactly fills a page; at $R=256$ it is $4{,}100$ bytes, spilling by $4$ bytes. The $255\to256$ change is $0.392157\%$ in degree. Under this fixed aligned/full-record-read layout it changes one page read to two, not necessarily every real implementation’s physical I/O. Padding one node to one page consumes $409.6\,\mathrm{GB}$ on disk at this scale, not the unpadded $333.2\,\mathrm{GB}$ including degree counters. Int8 full-vector storage frees $2{,}304$ bytes and gives the same arithmetic ceiling $R\le831$; that is a layout ceiling, not a recommended graph degree. Read rounds and load. Assume $120$ uncached one-page reads and at most $4$ useful simultaneous reads per query. At least $\lceil120/4\rceil=30$ rounds are needed; exactly $30$ assumes dependencies never reduce useful concurrency. At $100\,\mathrm{\mu s}$ per round this component is $3.0\,\mathrm{ms}$ before queueing, CPU, cache misses and tail effects. A beam setting alone does not establish the read count or that concurrency. At $5{,}000$ QPS, demand is $600{,}000$ random IOPS and $2.4576\,\mathrm{GB/s}$ of $4\,\mathrm{KiB}$ read traffic. With $100\,\mathrm{\mu s}$ mean read service time, Little’s law requires about $60$ reads in flight across the workload. Saving ten such sequential rounds saves $1\,\mathrm{ms}$, one quarter only if a separate $4\,\mathrm{ms}$ I/O budget is assumed. The cited billion-point DiskANN result reports one $64\,\mathrm{GB}$ machine, over $5{,}000$ QPS, above $95\%$ recall@1 and mean latency below $3\,\mathrm{ms}$ under that study’s SIFT-scale setup. The $100$-million, $768$-dimensional read toy above does not independently reproduce or validate it. In particular, one billion $96$-byte resident codes alone would need $96\,\mathrm{GB}$, so that code width cannot simply be transplanted to the reported $64\,\mathrm{GB}$ case. Practice. Sweep $\alpha$, degree and I/O beam on the actual data. Values such as $\alpha=1.2$ or $1.5$ are starting configurations, not hop guarantees; $\alpha=1$ is not mathematically restricted to RAM. Check the actual packed record layout and useful read concurrency before increasing degree. Wider I/O search can help latency or recall but can also raise total reads and saturation. Compare a missed query with exact search under matching filters and snapshot; then distinguish reachability, candidate stopping, distance distortion and representation issues. Cache frequently visited entry neighborhoods in RAM—Vamana is not inherently a layered graph. FreshDiskANN is the named update-oriented variant; tombstones, repair and rebuild cadence remain implementation choices. A single-box design fails its throughput target if peak IOPS, bandwidth or tail latency saturates, regardless of adequate average recall.