The shape of the problem: N vectors x d dimensions -> exact search costs O(N x d) per query -> too slow at scale -> APPROXIMATE indexes (HNSW graphs, IVF partitions, quantization) trade a little RECALL for a lot of SPEED and MEMORY -> but real queries have FILTERS (tenant, ACL, type), CHURN (updates, deletes), VERSIONS (embedding models), and ADVERSARIES -> so the engineering is in the interactions: recall x latency x memory x freshness x security x cost 

COMMON DIMENSIONS 384 · 512 · 768 · 1,024 · 1,536 · 3,072 (and more) — larger models and "large" variants tend to use more. MEANING OF EACH DIMENSION None individually. The model learns a space where DISTANCE and DIRECTION encode similarity; no single coordinate means "sports" or "formal." 

MEMORY PER VECTOR = dimensions x bytes per dimension float32 (4 B): 384-d = 1.5 KiB 768-d = 3 KiB 1,536-d = 6 KiB 3,072-d = 12 KiB float16 (2 B): half of that int8 (1 B): a quarter binary (1 bit): 1/32 AT SCALE float32 int8 binary 1 M x 768-d 2.9 GiB 0.7 GiB 0.09 GiB 1 M x 1,536-d 5.7 GiB 1.4 GiB 0.18 GiB 1 M x 3,072-d 11.4 GiB 2.9 GiB 0.36 GiB 100 M x 1,536-d 572 GiB 143 GiB 17.9 GiB COMPUTE Every distance calculation is O(d): double the dimensions, roughly double the arithmetic per comparison (and memory bandwidth per visited vector). INDEX Graph and list structures add overhead on top (Section 14), and high dimensions make approximate indexes work harder (below). 

In very high-dimensional spaces, distances between random points concentrate: the nearest and farthest neighbors become similar in distance, so "nearest" is less discriminating and index structures prune less effectively. In practice: - Real embeddings are NOT random; they lie near a much lower-dimensional manifold (low "intrinsic dimensionality"), which is why ANN indexes still work well at 1,536 or 3,072 dimensions. - But higher dimensions DO mean more memory, slower distance computations, and harder recall/speed trade-offs. - More dimensions is not automatically better retrieval: evaluate on your task. Many applications lose little quality going from 3,072 to 1,024 or even 512 dimensions. 

Some embedding models are trained with "Matryoshka" representation learning: the most important information is packed into the FIRST dimensions, so you can TRUNCATE the vector (keep the first 256, 512, or 1,024 values) and then RE-NORMALIZE it, retaining much of the quality at a fraction of the cost. Hosted APIs often expose this as a "dimensions" parameter. Truncating a model that was NOT trained this way degrades quality badly. 

public static class VectorMath { public static float[] Normalize(float[] v) { float norm = TensorPrimitives.Norm(v); // L2 length if (norm == 0) return v; var result = new float[v.Length]; TensorPrimitives.Divide(v, norm, result); // scale to unit length return result; } // Matryoshka-style reduction: keep the first `dims` values, then RE-NORMALIZE (cosine/dot assume unit vectors) public static float[] TruncateAndNormalize(float[] v, int dims) => Normalize(v.AsSpan(0, dims).ToArray()); public static float Dot(float[] a, float[] b) => TensorPrimitives.Dot(a, b); public static float L2(float[] a, float[] b) => TensorPrimitives.Distance(a, b); public static float Cosine(float[] a, float[] b) => TensorPrimitives.CosineSimilarity(a, b); } 

START from the model's native size; then TEST smaller sizes (via the API's dimensions option or truncation where the model supports it) on your benchmark. If quality holds at 1,024 or 512 dimensions, you cut memory, index size, and latency proportionally — often the cheapest scaling lever there is (Section 12). RECORD the dimension count in the index schema and with every stored vector's embedding spec (Section 10); a dimension mismatch is a hard error in most engines, and a silent one (truncated or padded) in some. LIMITS: engines cap dimensions per vector or per index (for example, some index types cap at a few thousand dimensions). Check the limits BEFORE choosing a model. 

DOT PRODUCT (inner product) a · b = Σ a_i b_i Larger = more similar. Depends on BOTH direction and magnitude. COSINE SIMILARITY (a · b) / (‖a‖ ‖b‖) Range -1..1. Depends on DIRECTION only (the angle); ignores magnitude. EUCLIDEAN (L2) DISTANCE ‖a − b‖ = sqrt(Σ (a_i − b_i)²) Smaller = more similar. Depends on both direction and magnitude (straight-line distance). (Others: Manhattan/L1 distance; Hamming distance for binary vectors; "cosine distance" = 1 − cosine similarity.) 

‖a − b‖² = ‖a‖² + ‖b‖² − 2 (a · b) = 2 − 2 (a · b) = 2 (1 − cos(a, b)) (because ‖a‖ = ‖b‖ = 1, and a · b = cos(a, b)) THEREFORE for normalized vectors: dot product = cosine similarity Euclidean distance² = 2 − 2 x cosine -> all three produce the IDENTICAL ranking of neighbors. Worked example: a = [0.6, 0.8] b = [1, 0] (both unit length) cosine = 0.6 dot = 0.6 L2² = (0.4)² + (0.8)² = 0.80 = 2 − 2 x 0.6 ✓ 

float[] a = VectorMath.Normalize([0.6f, 0.8f]); float[] b = [1f, 0f]; float cosine = VectorMath.Cosine(a, b); // 0.60 float dot = VectorMath.Dot(a, b); // 0.60 — same, because both are unit length float l2sq = MathF.Pow(VectorMath.L2(a, b), 2); // 0.80 = 2 - 2 * 0.60 

1. USE WHAT THE MODEL WAS TRAINED FOR. The embedding model's documentation says which metric its vectors are meant for. Most text embedding models: cosine (equivalently dot product on normalized output). 2. IF VECTORS ARE NORMALIZED -> DOT PRODUCT. It's the cheapest (no norms to compute), and ranks identically to cosine and L2. Many engines' fastest path is inner product on unit vectors. 3. IF VECTORS ARE NOT NORMALIZED: COSINE when magnitude is an artifact (typical for text embeddings) and you want pure semantic direction. DOT when magnitude carries meaning (for example, popularity or confidence encoded in the norm, as in some recommender models) and you WANT it to influence ranking — "maximum inner product search" (MIPS). L2 when the space's geometry is distance-based (some image/vision embeddings; clustering) and magnitude is meaningful. 4. BINARY VECTORS -> HAMMING distance (count of differing bits), the natural metric for binary-quantized embeddings (Section 12). 5. NORMALIZE ON WRITE (and for queries) so you can switch among cosine, dot, and L2 later without re-embedding, and so every metric agrees. 

INDEX METRIC MUST MATCH QUERY METRIC An HNSW/IVF index is built for ONE metric. Querying with another either fails, silently ignores the index (a full scan), or returns wrong neighbors. (pgvector: the operator class in CREATE INDEX — vector_cosine_ops, vector_ip_ops, vector_l2_ops — must match the operator in ORDER BY: <=>, <#>, <->.) DISTANCE vs. SIMILARITY Engines often return DISTANCES (smaller is better) rather than similarities. pgvector's <#> returns the NEGATIVE inner product so ORDER BY ascending works. Convert for display: cosine similarity = 1 − cosine distance; dot similarity = −(<#> value). MAGNITUDE SURPRISES Using dot product on UNNORMALIZED text embeddings lets long or "confident" vectors dominate rankings — usually not what you want. MIXED SOURCES Mixing normalized and unnormalized vectors in one index breaks dot-product and L2 rankings; enforce normalization in the ingestion pipeline and assert it in tests. SCORE THRESHOLDS A similarity cutoff ("keep > 0.80") is meaningful only for ONE model and metric; re-calibrate whenever either changes. HIGH SIMILARITY ≠ RELEVANCE Embedding similarity is a retrieval heuristic; use rerankers and thresholds calibrated on labeled data (see Advanced RAG Architecture, Section 12). 

// Brute-force top-k by dot product (assumes unit vectors, so this equals cosine). Exact, O(N x d) — the ground truth for measuring ANN recall. public static List<(int Id, float Score)> ExactTopK(IReadOnlyList<float[]> vectors, float[] query, int k) { var heap = new PriorityQueue<int, float>(); // min-heap: the root is the WORST of the current top-k for (int i = 0; i < vectors.Count; i++) { float score = TensorPrimitives.Dot(vectors[i], query); if (heap.Count < k) heap.Enqueue(i, score); else if (heap.TryPeek(out _, out float worst) && score > worst) heap.EnqueueDequeue(i, score); // replace the worst } var results = new List<(int, float)>(heap.Count); while (heap.TryDequeue(out int id, out float score)) results.Add((id, score)); results.Reverse(); // best first return results; } 

RECALL@k = | ANN top-k ∩ exact top-k | / k Recall@10 = 0.95 means the ANN index returned, on average, 9.5 of the 10 true nearest neighbors. It is measured against EXACT search on a sample of queries — there is no other ground truth for "nearest." Recall is a property of (index + parameters + data + filters). It must be MEASURED on your data; defaults and public benchmarks don't transfer. 

public static double RecallAtK(IReadOnlyList<int> approximate, IReadOnlyList<int> exact, int k) => approximate.Take(k).Intersect(exact.Take(k)).Count() / (double)k; // Average over many queries (use a few hundred representative ones; hold their exact answers as ground truth) double MeanRecall(IEnumerable<(IReadOnlyList<int> Approx, IReadOnlyList<int> Exact)> results, int k) => results.Average(r => RecallAtK(r.Approx, r.Exact, k)); 

GRAPH-BASED Build a proximity graph; search by greedy traversal toward the query. HNSW (Section 4), DiskANN/Vamana (graph on SSD + compressed vectors in RAM). Best recall/latency trade-off in RAM; heavier build and memory; hard to update and delete cleanly. PARTITION-BASED Divide space into cells; search only the nearest cells. IVF (Section 5), plus variants. Cheaper to build and smaller; needs training; recall tied to how many cells you probe. QUANTIZATION-BASED Compress vectors (scalar/int8, binary, product quantization) for smaller memory and faster approximate scoring; usually combined with the above and with RESCORING. TREE-BASED Space-partitioning trees (for example Annoy's random-projection forests). Simple and read-mostly; generally superseded by graphs for high-dimensional text embeddings. HASH-BASED Locality-sensitive hashing (LSH). Theoretically elegant, rarely the best in practice for embeddings today. HYBRID COMBINATIONS IVF-PQ, HNSW + scalar quantization, DiskANN + PQ — real engines mix techniques (e.g. a compressed index for candidate generation, full-precision vectors to rescore). 

 RECALL (accuracy) /\ / \ / \ LATENCY ------- MEMORY / COST Every index parameter moves you along these axes: examine more candidates (higher recall, slower), store more links or full-precision vectors (higher recall, more memory), compress (less memory, lower recall unless you rescore). There is no free setting — only the right trade-off for your latency SLO, recall target, and budget. Section 12 shows how to find it empirically. 

USE EXACT SEARCH WHEN - N is small (thousands to a few hundred thousand, depending on dimensions and hardware) — a brute-force SIMD scan can be faster than maintaining an index. - A FILTER is highly selective (only a few thousand candidates match) — score the filtered set exactly (Section 6). - You need a perfect-recall BASELINE for evaluation, or a fallback when an ANN query returns too few results. - Recall requirements are strict (compliance and discovery workloads). Most engines offer an exact/"flat" mode alongside ANN indexes for exactly these cases. 

LAYER 2 (very sparse): o─────────────────o <- long-range "express lanes"; few nodes LAYER 1 (sparser): o────o────o───────o────o────o LAYER 0 (ALL vectors): o─o─o─o─o─o─o─o─o─o─o─o─o─o─o─o─o─o─o <- every vector, linked to its nearest neighbors SEARCH: start at the entry point in the top layer ──> greedily hop to whichever neighbor is closer to the query ──> when no neighbor is closer, DROP to the next layer at that node ──> repeat down to layer 0 ──> at layer 0 run a best-first (beam) search that keeps the `ef` best candidates, expanding the closest unvisited ones ──> return the best k. 

EACH NEW VECTOR 1. LEVEL: draw a random maximum layer (exponentially decaying: most vectors only live on layer 0; roughly 1 in M reaches layer 1, 1 in M² layer 2...). 2. DESCEND from the entry point to find its place, as in a search. 3. At each layer from its level down to 0: search for the efConstruction nearest candidates, then CONNECT to up to M of them (layer 0 allows up to 2M links), choosing neighbors with a DIVERSITY heuristic (prefer neighbors that aren't already close to each other, preserving long-range links). 4. Add reverse links; if a neighbor exceeds its link limit, prune its weakest links. Insertion is incremental — no global training step — but each insert costs a search, so BUILD is expensive and parallelism is limited by graph contention. 

M Max links per node (layer 0 holds up to 2M). Higher M = better recall, especially on hard/high-dimensional data, and denser graphs — but more memory, slower build, slower queries. Typical 16-48. efConstruction Candidate-list size during BUILD. Higher = a better-connected graph (higher achievable recall) and slower, costlier builds. Typical 100-400+. Set once at build time; changing it means rebuilding. efSearch (ef) Candidate-list size at QUERY time (must be >= k). THE main runtime knob: higher = higher recall and higher latency. Typical 40-500. Tunable per query/session with no rebuild. (pgvector: m = 16, ef_construction = 64, hnsw.ef_search = 40 are defaults; Azure AI Search documents its own defaults. Defaults are conservative starting points, not recommendations for your data.) RULES OF THUMB - Raise efSearch FIRST (free, instant) until recall plateaus or latency breaks your SLO. - If recall plateaus below target even at high efSearch, the graph is the limit: rebuild with higher M and/or efConstruction. - High-dimensional, clustered, or hard datasets need larger M; small low-dimensional ones need less. - Recall depends on k: asking for top-100 at the efSearch tuned for top-10 hurts recall; efSearch should scale with k. 

// A single-layer proximity graph with beam search — the layer-0 half of HNSW. Real HNSW adds the sparse upper layers for fast long-range navigation // and builds incrementally in O(log N)-ish per insert; this toy builds by brute force (O(N²)) purely for illustration. Vectors must be unit-length. public sealed class ToyNswIndex { private readonly IReadOnlyList<float[]> _vectors; private readonly int[][] _neighbors; public ToyNswIndex(IReadOnlyList<float[]> vectors, int m) { _vectors = vectors; var links = new HashSet<int>[vectors.Count]; for (int i = 0; i < links.Length; i++) links[i] = []; // Link every vector to its M nearest neighbors, in BOTH directions (bidirectional links keep the graph navigable) Parallel.For(0, vectors.Count, i => { int[] nearest = Enumerable.Range(0, vectors.Count).Where(j => j != i) .OrderByDescending(j => TensorPrimitives.Dot(vectors[i], vectors[j])).Take(m).ToArray(); lock (links) foreach (int j in nearest) { links[i].Add(j); links[j].Add(i); } }); _neighbors = links.Select(s => s.ToArray()).ToArray(); } public List<(int Id, float Score)> Search(float[] query, int k, int ef, int entryPoint = 0) { var visited = new HashSet<int> { entryPoint }; var candidates = new PriorityQueue<int, float>(); // best-first frontier (min-heap on NEGATIVE score => best candidate pops first) var results = new SortedSet<(float Score, int Id)>(); // the ef best found so far (ascending by score; Min = worst kept) float entryScore = TensorPrimitives.Dot(query, _vectors[entryPoint]); candidates.Enqueue(entryPoint, -entryScore); results.Add((entryScore, entryPoint)); while (candidates.TryDequeue(out int current, out float negScore)) { // Stop when the best remaining candidate is worse than everything we're keeping: no neighbor of it can improve the result set if (results.Count >= ef && -negScore < results.Min.Score) break; foreach (int neighbor in _neighbors[current]) { if (!visited.Add(neighbor)) continue; float score = TensorPrimitives.Dot(query, _vectors[neighbor]); if (results.Count < ef || score > results.Min.Score) { candidates.Enqueue(neighbor, -score); results.Add((score, neighbor)); if (results.Count > ef) results.Remove(results.Min); // keep only the ef best } } } return results.Reverse().Take(k).Select(r => (r.Id, r.Score)).ToList(); } } // Increase `ef` and recall rises while more vectors are scored (higher latency): the efSearch trade-off in 40 lines. 

MEMORY-HUNGRY, RAM-RESIDENT The graph and (usually) the full vectors must be in memory for fast queries: traversal is random access. If the index spills out of RAM, latency collapses ("falls off a cliff"). Plan memory with headroom (Section 14); consider quantization or disk-oriented designs (DiskANN) beyond RAM. BUILD COST Building and rebuilding large HNSW indexes takes real time and memory; parameters like efConstruction multiply it. Build off the serving path. INSERTS ARE EASY Incremental inserts work without retraining. DELETES AND UPDATES ARE HARD Removing a node punches a hole in the graph and can disconnect regions. Engines use tombstones (deleted flags) and later repair or rebuild; heavy churn degrades recall and wastes memory until compaction/reindex (Section 9). An update is usually delete + insert. FILTERS ARE HARD A filter that rejects most nodes can leave the traversal with nowhere to go (Section 6). RECALL IS ALWAYS < 100% Even a well-tuned index misses a few true neighbors; it is stochastic in construction (random levels), so two builds differ slightly. CONCURRENCY Reads scale well; concurrent writes contend. Many engines use segments (see below). SEGMENTED ENGINES Several systems build one HNSW graph PER SEGMENT and merge periodically; a query searches all segments and merges top-k. More segments = more fan-out latency; merge/compaction policy matters. 

TRAIN: run k-means over (a sample of) the vectors -> nlist centroids (cell centers) ADD: assign each vector to its nearest centroid -> inverted lists: centroid 17 -> [vector ids...] QUERY: 1. compare the query to the nlist centroids (cheap: nlist << N) 2. pick the nprobe closest cells 3. scan ONLY the vectors in those cells (exactly, or approximately if compressed), return the top k Work per query ≈ nlist + (nprobe / nlist) x N vector comparisons — a fraction of the exact scan. 

nlist Number of cells. Common guidance: roughly sqrt(N) to 4 x sqrt(N) (pgvector suggests about N/1000 for up to ~1 M rows and sqrt(N) beyond). More cells = smaller lists = faster scans per probe, but more probes needed for the same recall and a costlier assignment step. nprobe Cells searched per query. THE runtime knob: higher = higher recall, slower. Often starts near sqrt(nlist); at nprobe = nlist it's an exact search. (pgvector: ivfflat.probes.) TRAINING DATA Centroids must reflect the real distribution: train on representative data (for pgvector IVFFlat, build the index AFTER loading data). If the data drifts, the clusters get stale. 

// k-means partitioning + nprobe scanning (unit vectors, dot-product similarity). Educational: real engines use k-means++ init, mini-batch training, SIMD scans, and compressed lists. public sealed class ToyIvfIndex { private readonly IReadOnlyList<float[]> _vectors; private readonly float[][] _centroids; private readonly List<int>[] _lists; public ToyIvfIndex(IReadOnlyList<float[]> vectors, int nlist, int iterations = 10, int seed = 1) { _vectors = vectors; <...