Advanced Vector Databases & Retrieval Algorithms¶

1. Exact k-Nearest Neighbors (k-NN) vs. Approximate Nearest Neighbors (ANN)¶

In a metric space $(X, d)$, given a query vector $q \in \mathbb{R}^d$ and a dataset $S = \{x_1, x_2, \dots, x_N\} \subset \mathbb{R}^d$, exact k-NN retrieval requires computing $d(q, x_i)$ for all $i \in [1, N]$, yielding a time complexity of $O(N \cdot d)$. As $N \to 10^8+$ and $d \sim 768-4096$, linear scanning becomes computationally intractable for low-latency ($<10$ms) SLAs.

To break the $O(N)$ bound, we relax the problem to Approximate Nearest Neighbors (ANN). The objective shifts to finding a point $p \in S$ such that $d(q, p) \le (1+\epsilon) d(q, p^*)$, where $p^*$ is the true nearest neighbor. This enables sub-linear query times, typically $O(\log N)$ or $O(1)$, trading off recall for throughput.

Distance metrics commonly employed: * Cosine Similarity: $S_C(A, B) = \frac{A \cdot B}{\|A\|_2 \|B\|_2}$. Equivalent to squared $L_2$ distance when vectors are normalized onto the unit hypersphere. * Inner Product (IP): $IP(A, B) = A \cdot B$. Useful when vector magnitude carries semantic weight (e.g., non-normalized embeddings). * $L_2$ Distance: $L_2(A, B) = \|A - B\|_2$.

2. Hierarchical Navigable Small World (HNSW)¶

HNSW is currently the state-of-the-art graph-based ANN algorithm, combining the concepts of skip-lists and Navigable Small World (NSW) graphs. It constructs a multi-layered proximity graph where each layer represents a Voronoi diagram approximation.

2.1 Graph Architecture and Construction¶

The structure consists of $L$ layers. The top layer (layer $L-1$) contains a sparsely connected subset of points. As we descend to layer 0, the node density increases, with layer 0 containing all $N$ elements.

During insertion of a new element $q$, we randomly assign it a maximum layer $l = \lfloor - \ln(\text{unif}(0,1)) \cdot m_L \rfloor$, where $m_L$ is a normalization factor. For layers $> l$, we simply traverse the graph to find the nearest neighbor to act as an entry point for the next layer. For layers $\le l$, we perform a greedy search to find the $ef\_construction$ nearest neighbors, and create bidirectional links between $q$ and $M$ of these neighbors.

2.2 Search Complexity and Parameters¶

Routing in HNSW begins at the top layer. We greedily traverse to the local minimum, then drop down a layer, using the previous minimum as the entry point. This provides $O(\log N)$ expected search complexity.

Crucial Hyperparameters: * M: The maximum number of outgoing connections in the graph per node per layer. Higher M increases memory consumption $O(M \cdot N)$ and graph construction time, but improves recall for high-dimensional data. * ef_construction: The size of the dynamic candidate list during insertion. Determines the neighborhood exploration depth when building the Delaunay graph approximation. Computational complexity during construction scales with $O(N \cdot \text{ef\_construction} \cdot \log N)$. * ef_search: The size of the dynamic candidate list during querying at layer 0. Higher ef_search yields higher recall at the cost of linearly scaling the distance computations at the lowest level.

3. Product Quantization (PQ)¶

While HNSW provides exceptional latency and recall, uncompressed vector storage is RAM-bound. 1 billion 768-dimensional float32 vectors require $\approx 3$ TB of RAM. PQ compresses vectors by decomposing the high-dimensional space into lower-dimensional subspaces and quantizing each independently.

3.1 Subspace Decomposition¶

A vector $x \in \mathbb{R}^d$ is split into $m$ contiguous sub-vectors $x = [x^1, x^2, \dots, x^m]$, where each $x^i \in \mathbb{R}^{d/m}$. For each subspace $i$, k-means clustering is applied on the training data to generate a codebook $C^i = \{c^i_1, c^i_2, \dots, c^i_k\}$ of $k$ centroids.

3.2 Asymmetric Distance Computation (ADC)¶

A vector is quantized by mapping each sub-vector $x^i$ to its nearest centroid index in $C^i$. The compressed vector uses $m \cdot \log_2(k)$ bits. Typically, $k=256$ (1 byte per subspace), reducing a 768d float32 vector (3072 bytes) to $m$ bytes (e.g., $m=96$ gives a 32x compression).

During retrieval, given a query $q = [q^1, q^2, \dots, q^m]$, the ADC estimates the distance to a quantized database vector $y$: $$ \tilde{d}(q, y) = \sum_{j=1}^m d(q^j, c^j_{y^j}) $$ Instead of computing distances to $N$ vectors, we precompute a lookup table (LUT) of distances between each query sub-vector $q^j$ and all $k$ centroids in $C^j$. The complexity drops from $O(N \cdot d)$ to $O(d \cdot k + N \cdot m)$.

4. Sparse vs. Dense Retrieval¶

4.1 BM25 (Sparse)¶

BM25 relies on inverted indices mapping vocabulary terms to documents. It evaluates exact lexical overlap. $$ \text{BM25}(q, D) = \sum_{i=1}^{|q|} IDF(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{\text{avgdl}})} $$ BM25 scales exceptionally well (sub-millisecond lookups via posting lists) and guarantees precise keyword matching, but fails on semantic synonymy (the vocabulary mismatch problem).

4.2 Embedding-based (Dense)¶

Dense retrieval projects queries and documents into a shared continuous embedding space using bi-encoders (e.g., BERT). It captures semantic intent but struggles with rare entities, serial numbers, or out-of-domain vocabulary where the model lacks representational capacity. Production systems typically utilize Hybrid Search (fusion of BM25 and Dense scores via Reciprocal Rank Fusion or linear interpolation).

5. Advanced RAG Indexing Architectures¶

5.1 ColBERT and Late Interaction¶

Standard dense retrieval computes a single $d$-dimensional vector per document (bottlenecking the representational capacity of long texts). ColBERT (Contextualized Late Interaction over BERT) encodes the query into $N_q$ token-level vectors and the document into $N_d$ token-level vectors. The scoring function is a sum of maximum similarities: $$ S(Q, D) = \sum_{i \in Q} \max_{j \in D} (E_{Q_i} \cdot E_{D_j}) $$ This "late interaction" enables fine-grained token-level semantic matching, dramatically improving recall over single-vector bi-encoders, at the cost of vastly larger storage requirements ($O(\text{tokens} \cdot d)$).

5.2 Chunking Strategies at Production Scale¶

Document partitioning dictates embedding quality. * Fixed-Size Chunking with Overlap: Naive but performant. Chunks of size $C$ tokens with overlap $O$. May break semantic boundaries. * Hierarchical/Parent-Child Indexing: Small chunks are embedded for highly precise retrieval. A pointer maps the retrieved child chunk to its parent (the entire section or document) for context injection into the LLM context window. * Semantic Chunking: Utilizing sentence-transformers to calculate pairwise cosine similarities between adjacent sentences. When similarity drops below a threshold $\tau$, a chunk boundary is defined, preserving semantic cohesion.