Vector search, simulated

Data. The playground dataset that the HNSW, IVF, PQ and Metrics tabs share: Gaussian clusters, uniform points, a low-dimensional subspace (3 intrinsic dimensions inside d plus a little noise) or concentric rings; n up to 2,000 and d up to 128, with a seed. Forty held-out queries come from the same distribution. Upload vectors takes CSV/TSV (a header row and an id column are skipped), a JSON array, JSON lines with an embedding field, or .fvecs (the SIFT/GIST format). With d = 2 you see exactly what the index searches and can click anywhere to put your own query; with d > 2 the picture is a PCA projection on the two main components (their share of the variance is shown) while every index searches all dimensions, and a click moves to the next held-out query.

HNSW. Hierarchical navigable small world graphs (Malkov & Yashunin). Each node draws a level l = ⌊−ln(U)·mL⌋ with mL = 1/ln M, so a fraction 1/M of nodes reaches layer 1, 1/M² layer 2 and so on; the table compares the layer sizes with n·M^−l. Search steps through a query: enter at the top layer’s entry point, greedy search with ef = 1 on each upper layer (the dashed violet route), then best-first search with ef = max(efSearch, k) on layer 0. Each step expands one candidate: green lines go to neighbours that made it into the ef best (W), grey dashes to those that did not, blue dots are every node whose distance was computed. The last step shows the k results, the true k nearest (gold rings), recall and the number of distance computations against brute force. Build (insert) steps through inserting one node (pick it with the slider): its level, the greedy descent, the efConstruction candidates on each of its layers, which links the selection keeps (green) or drops (red dashes to the neighbour that "covers" them), and neighbours over the cap (Mmax0 = 2M on layer 0, M above) shrinking their lists (red ✕). Heuristic is the paper’s Algorithm 4 as hnswlib and Lucene use it; Simple keeps the M closest (Algorithm 3) — try it on tight clusters. The thumbnails show every layer; tap one to pin it.

IVF. An inverted file with a k-means coarse quantizer. Train steps through k-means++ seeding and each Lloyd iteration (points coloured by cell, centroids ✕, Voronoi cells shaded in 2-D, inertia falling). Search ranks the nlist centroids, probes the nprobe nearest cells, scans their lists one by one and shows the result; true neighbours in unprobed cells get red rings — put the query near a cell boundary to see why nprobe matters.

PQ & quantization. A product quantizer with m sub-vectors and 2^bits centroids per sub-space (m must divide d). In 2-D with m = 2 you see the product grid of 2^bits × 2^bits possible reconstructions and a line from every vector to its code’s reconstruction. The ADC card shows the query’s lookup table (rows are centroids, columns sub-spaces) with the codes of the best match highlighted: the sum of its lookups equals the exact distance to its reconstruction. Recall@k is compared for PQ, PQ re-ranked with exact distances on 4k candidates, int8 scalar quantization and binary codes with and without re-ranking; the compression table gives bytes per vector and the mean squared error. show switches the picture to the int8 reconstruction or the binary codes (in 2-D, the two sign bits are the quadrant around the mean).

Metrics. The same query ranked by L2, cosine and dot product, with the boundary through each metric’s k-th match: a circle for L2, a cone from the origin for cosine, a line perpendicular to the query for the dot product. Notes cover normalisation, why −q·x is not a metric, and the operator names in pgvector, Elasticsearch/OpenSearch and faiss.

Benchmark. Up to 20,000 vectors of up to 256 dimensions (generated, or your own upload) with 200 queries. Pick the indexes, their build parameters, the metric and k, and Run. Each index is built once and its search parameter swept — efSearch for HNSW, nprobe for IVF-Flat and IVF-PQ, the re-rank factor for PQ, int8 and binary. Two charts plot recall@k against work per query and against memory, with brute force as the reference line; every point is in the table. A PCA picture of the data shows the first query and its true neighbours.

The visual tabs use up to 2,000 vectors (they run on the main thread so every step can be drawn); the benchmark takes 20,000. Everything is single-threaded JavaScript, so absolute times mean little; distance counts are exact.

HNSW follows the paper’s algorithms with the heuristic of Algorithm 4 without extendCandidates or keepPrunedConnections (the hnswlib and Lucene defaults); deletions, filtering and concurrent inserts are not modelled. Lucene’s HNSW and hnswlib differ in small details (Lucene’s level assignment uses the same mL = 1/ln M).

IVF-PQ encodes residuals from the coarse centroid and builds a lookup table per probed list; faiss’s precomputed-table trick, OPQ rotations, polysemous codes and fast-scan 4-bit SIMD are not modelled. int8 uses one min/max per dimension (no confidence intervals or per-vector corrections as in Lucene’s optimised scalar quantization), and binary is the plain sign code after centring.

k-means always runs in L2; on normalised vectors (cosine) that orders like spherical k-means.

Uploaded vectors live only in this page while it is open; share links never include them.

Yu. A. Malkov and D. A. Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, arXiv:1603.09320 (2016); IEEE TPAMI 42(4), 2020 (online 2018). Algorithms 1–5, mL = 1/ln M, Mmax0 = 2M.

H. Jégou, M. Douze and C. Schmid, Product quantization for nearest neighbor search, IEEE TPAMI 33(1), 2011 — ADC and IVFADC (IVF-PQ on residuals).

J. Sivic and A. Zisserman, Video Google, ICCV 2003 (the inverted file over a k-means vocabulary); D. Arthur and S. Vassilvitskii, k-means++, SODA 2007.

The faiss wiki (github.com/facebookresearch/faiss/wiki): index factory, guidelines for nlist, IndexHNSW, IndexIVFPQ and IndexRefine; hnswlib; Lucene’s HnswGraphBuilder and Lucene99HnswVectorsFormat; the Elasticsearch dense_vector reference (similarity options and quantization); the pgvector README (operators, HNSW and IVFFlat parameters).

Y. Bachrach et al., Speeding up the Xbox recommender system using a Euclidean transformation for inner-product spaces, RecSys 2014 (MIPS → nearest neighbour).