Vector databases and similarity search

ANN algorithms trade a small amount of recall (the fraction of true nearest neighbors actually returned) for dramatically lower query latency and better scalability. Exact k-NN guarantees correct results but requires comparing the query against every vector (O(N) brute force), or uses exact structures that degrade in high dimensions. ANN accepts approximate results to achieve sub-linear search at scale.

HNSW builds a hierarchy of proximity graphs where upper layers are sparse (long-range links) and lower layers are dense (short-range links). Search starts at the top layer and greedily descends, using upper layers as an express highway to quickly approach the query region before fine-grained search at layer 0. This yields roughly logarithmic search complexity with high recall.

Text embeddings frequently encode semantic meaning in their direction/orientation rather than magnitude, and magnitude can correlate with token frequency or document length rather than meaning. Cosine similarity measures the angle between vectors, ignoring magnitude, so it focuses on semantic orientation. Note that for L2-normalized vectors, ranking by cosine similarity and by Euclidean distance are equivalent.

PQ splits each vector into m sub-vectors and quantizes each sub-vector independently using a small learned codebook (e.g., 256 centroids = 1 byte each), storing only the centroid IDs. This compresses vectors massively (e.g., a 768-dim float32 vector down to m bytes) and enables fast approximate distance computation via precomputed lookup tables (ADC). It is key for fitting billion-scale indexes in RAM at the cost of some accuracy.

nlist is the number of Voronoi cells (clusters) the vector space is partitioned into during training via k-means. nprobe is the number of nearest cells searched at query time. Higher nprobe increases recall (searches more cells) but raises latency; nlist affects the granularity of partitioning and the speed/accuracy balance.

As dimensionality grows, distances between points become increasingly uniform - the contrast between nearest and farthest neighbors shrinks - making nearest-neighbor queries less meaningful and harder to accelerate. Tree-based exact methods (e.g., KD-trees) degrade to near-linear scans, and data becomes sparse. This motivates ANN methods (HNSW, IVF-PQ) and careful embedding/dimensionality choices.

M (max number of bidirectional links per node) controls graph connectivity - higher M improves recall and query speed but increases memory and build time. efConstruction controls the candidate list size during index building (higher = better graph quality, slower build), while efSearch controls the candidate list at query time (higher = better recall, slower queries).

Filtered search combines vector similarity with structured metadata constraints (e.g., 'similar docs WHERE category=finance'). Post-filtering retrieves top-k by vector then drops non-matching results, which can return too few items if the filter is selective. Pre-filtering restricts the candidate set before/during graph traversal, preserving recall but complicating ANN index traversal; modern systems use filtered-HNSW or hybrid strategies to balance recall and speed.

Hybrid search runs both a dense semantic retriever and a sparse keyword retriever (e.g., BM25 or SPLADE), then fuses the ranked lists - commonly with Reciprocal Rank Fusion (RRF) or a weighted score combination. This captures both semantic similarity and exact keyword matches (names, codes, rare terms), improving robustness over either method alone.

# Reciprocal Rank Fusion
def rrf(rank_lists, k=60):
    scores = {}
    for ranks in rank_lists:
        for r, doc in enumerate(ranks):
            scores[doc] = scores.get(doc, 0) + 1/(k + r + 1)
    return sorted(scores, key=scores.get, reverse=True)

For unit-normalized vectors, cosine similarity equals the dot product, and squared Euclidean distance equals 2 - 2*cos(theta). Thus ranking by maximum dot product, maximum cosine, or minimum L2 distance all produce identical neighbor orderings. This lets systems normalize once and use the fastest available metric (often inner product).

Recall@k is the fraction of the true k nearest neighbors (from exact/brute-force search as ground truth) that appear in the ANN index's top-k results, averaged over a query set. It is the standard accuracy metric for tuning ANN systems, typically plotted against queries-per-second (QPS) to characterize the speed/accuracy trade-off curve.

Inner product violates the triangle inequality and is not self-maximizing - a vector with larger magnitude can have a higher inner product with the query than the query itself, so a point need not be its own nearest neighbor. This breaks standard metric-tree assumptions. A common workaround augments each vector with an extra dimension to convert MIPS into an equivalent L2 nearest-neighbor problem, enabling metric-based ANN indexes.

ANN retrieval is optimized for speed and may use compressed/approximate vectors, so its top-k ordering can be imprecise. A re-ranking stage rescores the candidate set with a more expensive but accurate model - either full-precision vector distances or a cross-encoder that jointly encodes query and document - to improve final ordering and precision before passing context to the LLM.

A bi-encoder encodes query and document independently into vectors, enabling precomputation and fast ANN retrieval (vectors compared by similarity). A cross-encoder feeds the query-document pair jointly through a transformer, producing a much more accurate relevance score but at a cost that scales with the number of candidates scored per query. Pipelines use a bi-encoder for fast candidate retrieval and a cross-encoder to re-rank the small candidate set.

IVF-PQ combines an inverted-file (IVF) coarse quantizer that partitions vectors into clusters with Product Quantization (PQ) that compresses the residuals within each cluster. IVF limits the search to a few clusters (nprobe), and PQ makes each stored vector tiny while enabling fast table-lookup distance estimation. Together they give a low memory footprint and high throughput at billion scale, trading exactness for efficiency.

Sharding partitions the vector collection across nodes so each holds a subset - queries are scattered to all shards and results gathered/merged, increasing capacity and parallelism. Replication copies the same data across nodes for high availability and read throughput. Production systems combine both: shards for scale, replicas per shard for fault tolerance and QPS.

Scalar quantization maps each individual vector dimension from float32 to a lower-precision integer (e.g., int8) independently, giving roughly 4x compression with minimal accuracy loss and fast SIMD distance computation. PQ instead quantizes groups of dimensions (sub-vectors) jointly against learned codebooks, achieving far higher compression (e.g., 32x or more) but with more accuracy loss and a training step.

With naive post-filtering, the HNSW search returns top-k by vector similarity and then drops items failing the filter, which can yield far fewer than k matching results when the filter is selective. Mitigations include increasing efSearch/over-fetching, using filter-aware traversal (only expanding nodes passing the filter), or maintaining separate per-attribute indexes/partitions. Many vector DBs implement these as 'filtered HNSW'.

Higher dimensionality increases storage (bytes per vector), memory for in-RAM indexes, and per-comparison distance cost, raising both cost and latency. Lower dimensions are cheaper and faster but may lose semantic fidelity. Techniques like Matryoshka Representation Learning let a single model produce embeddings that can be truncated to smaller dimensions with graceful accuracy degradation, allowing cost/accuracy tuning.

RRF combines multiple ranked lists by summing 1/(k + rank) contributions for each document across lists (k is a constant, often 60). It is popular because it requires no score normalization - operating purely on ranks - making it robust to incomparable score scales (e.g., BM25 vs cosine) and simple to implement, while reliably improving fused quality.

DiskANN stores the bulk of the graph and full-precision vectors on SSD while keeping compressed vectors and a small graph cache in RAM, enabling billion-scale search on a single commodity machine at a fraction of the memory cost. The trade-off is somewhat higher latency due to SSD random reads, which it minimizes via its Vamana graph design and beam-search I/O batching.

Chunk size and overlap determine the granularity of embeddings: too-large chunks dilute the embedding with mixed topics (lower precision), while too-small chunks lose surrounding context (lower recall and fragmented answers). Effective strategies use semantic/structure-aware chunking, sensible overlap, and sometimes hierarchical or parent-document retrieval to balance precise matching with sufficient context.

HNSW supports incremental inserts naturally, but true deletions are hard because removing a node can disconnect the graph. Common approaches are soft deletes (mark as deleted, filter at query time) with periodic compaction/rebuild to reclaim space, or tombstoning. Frequent in-place deletions degrade graph quality over time, so many systems schedule background re-indexing.

It fixes the imprecision of fast first-stage ANN retrieval by fetching more candidates than needed (e.g., top-100 instead of top-10) and re-ranking them with a more accurate scorer, recovering relevant items the approximate stage may have mis-ordered. The main cost is added latency and compute from the expensive re-ranker, especially cross-encoders, on the enlarged candidate set.

LSH uses hash functions that map nearby points to the same bucket with high probability, so candidate neighbors are found by hashing the query and scanning matching buckets. It has theoretical guarantees and is simple and streaming-friendly, but in practice graph-based (HNSW) and quantization-based (IVF-PQ) methods generally achieve better recall/latency trade-offs, so LSH is now less common for high-accuracy needs.

GPUs excel at the massively parallel matrix/distance computations in brute-force and IVF search, giving huge throughput for batched queries and fast index training (k-means, PQ codebooks). Limits include finite GPU memory (constraining in-VRAM index size), host-device transfer overhead, and the fact that latency-sensitive single-query graph traversal (HNSW) is less GPU-friendly than batched, regular workloads.

Normalizing to unit length makes inner product equal to cosine similarity, so semantic comparisons are based on direction not magnitude - desirable for most embedding models. It also ensures consistent score ranges and lets you use the typically fastest inner-product index path while getting cosine semantics. You must normalize both stored vectors and queries identically.

import numpy as np
def l2_normalize(v):
    return v / (np.linalg.norm(v, axis=-1, keepdims=True) + 1e-12)

Latency is the time to answer a single query (often reported as p50/p95/p99), throughput (QPS) is how many queries the system handles per second (often via batching/concurrency), and recall is answer quality vs exact search. These trade off: raising efSearch/nprobe improves recall but worsens latency and lowers QPS, so benchmarks report recall-vs-QPS Pareto curves.

MRL trains embeddings so that the most important information is concentrated in the leading dimensions, meaning you can truncate a high-dimensional vector to a shorter prefix and still get strong accuracy. This lets one model serve multiple cost/accuracy points - use short vectors for cheap first-stage retrieval and full vectors for re-ranking - without retraining or storing multiple models.

IndexFlatL2 performs exact brute-force L2 search over all vectors - 100% recall but O(N) per query and full memory storage. IVF and HNSW are approximate indexes that prune the search space (clusters or graph traversal) for sub-linear latency at the cost of some recall, and IVF/PQ variants also compress vectors. Flat is the ground-truth baseline; the others scale to large datasets.

import faiss
idx = faiss.IndexFlatL2(d)   # exact baseline
idx.add(xb); D, I = idx.search(xq, k)

Instead of one vector per document, late-interaction models store a vector per token and score a query-document pair via MaxSim (sum over query tokens of the max similarity to any document token). This captures fine-grained term-level matching and improves accuracy, but greatly increases storage and query cost, requiring specialized indexing (e.g., PLAID) to remain practical.

As nprobe approaches nlist, the search scans nearly all clusters, approaching a brute-force scan - recall rises toward 100% but latency and CPU cost grow toward O(N), eliminating IVF's speed advantage. The goal is to find the smallest nprobe that meets the target recall, keeping queries fast while searching only the most promising clusters.

Embedding drift occurs when the embedding model changes (new version/finetune), producing vectors that are not comparable to those generated by the old model - mixing them corrupts similarity results. The correct handling is to re-embed the entire corpus with the new model into a new index and switch atomically (or run side-by-side and cut over), never mixing vector spaces, since query and stored vectors must come from the same model.