RAG & Vector Database - OpenML's AI & Quantum Computing Blogs

1583 words

8 minutes

RAG & Vector Database

2026-11-07

English

Technology

There is a chronological evolution in academics that lays the foundations of vector database.

Product Quantization for Nearest Neighbor Search
The Graph Standard: HNSW: Multi-layer skip-list graph topologies, logarithmic search complexity in high dimensions, beam search heuristic, and trade-offs between connectivity degree $M$ and exploration depth efSearch.
Billion-scale similarity search with GPUs
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node

The Graph Standard: HNSW#

Paper link
Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

The constantly growing amount of the available information resources has led to high demand in scalable and efficient similarity search data structures. One of the generally used approaches for information search is the $K$ -Nearest Neighbor Search ( $K$ -NNS). Unfortunately, the complexity of the naïve approach scales linearly with the number of stored elements making it infeasible for large-scale datasets.

To overcome this problem a concept of Approximate Nearest Neighbors Search ( $K$ -ANNS) was proposed.

Approximate Nearest Neighbor Search ( $K$ -ANNS) Algorithm#

$K$ -Nearest Neighbor Search ( $K$ -NNS) is the formal problem of retrieving the $K$ points in a dataset closest to a query point under a specified metric space $(X, d)$ , whereas $K$ -Approximate Nearest Neighbor Search ( $K$ -ANNS) relaxes this guarantee by trading mathematical exactness for sub-linear query time in high dimensions.

In exact $K$ -NNS, given:

A finite dataset $S \subset X$ of size $\vert{}S\vert{} = N$ , where $X \subseteq \mathbb{R}^D$
A distance metric $d: X \times X \to [0, \infty)$ (e.g., Euclidean distance $L_2$ , Cosine distance, or Manhattan distance $L_1$ )
A query vector $q \in X$ and integer $K \ge 1$

Exact $K$ -NNS finds a subset $R \subseteq S$ of cardinality $\vert{}R\vert{} = K$ such that:

\forall u \in R, \quad \forall v \in S \setminus R: \quad d(q, u) \le d(q, v)

For exact search, traditional space-partitioning structures such as $k\text{-d}$ trees or $R$ -trees require traversing nearly all bounding boxes once the intrinsic dimensionality $D \gtrsim 20$ . As $D$ grows large, the relative difference between the distance to the nearest neighbor and the furthest neighbor approaches zero ( $\lim_{D \to \infty} \frac{d_{\max} - d_{\min}}{d_{\min}} \to 0$ ) and partitioning methods degrade to an exhaustive linear scan with computational complexity $\mathcal{O}(N \cdot D)$ , both result in the Curse of Dimensionality.

To bypass such linear scaling, $K$ -ANNS permits an approximation error $\epsilon > 0$ . In the standard $(1 + \epsilon)$ -ANN definition, the algorithm returns a point $v \in S$ such that:

d(q, v) \le (1 + \epsilon) \cdot d(q, v^*)

where $v^*$ is the true nearest neighbor. In practical retrieval, this accuracy is measured empirically via Recall@ $K$ :

\color{green} \boxed{\text{Recall}@K = \frac{\vert{}R_{\text{approx}} \cap R_{\text{true}}\vert{}}{K}}

where $R_{\text{approx}}$ is the set of $K$ points returned by the index, and $R_{\text{true}}$ is the ground-truth exact set computed via brute-force search.

How $K$ -ANNS Works Under the Hood#

All $K$ -ANNS algorithms avoid scanning every vector by pruning the search space ahead of time using one of 4 foundational paradigms:

Tree-Based Space Partitioning (KD-Trees/Ball Trees/RP-Trees)

Recursively bisects the vector space into hierarchical bounding volumes. $k\text{-d}$ trees split space using axis-aligned orthogonal hyperplanes, Ball trees partition space using nested hyper-spheres, and Random Projection (RP) trees (like Spotify’s Annoy) split points using hyperplanes oriented along random directions.

Traversal descends the tree from the root to the leaf cell containing query $q$ in $\mathcal{O}(\log N)$ time, then backtracks across parent branches using priority queues to evaluate intersecting bounding regions.

Backtracking stops after visiting an inspection limit of leaf nodes (search_k). While exact branch-and-bound works well in low dimensions ( $D \lesssim 20$ ), high-dimensional queries intersect almost every bounding boundary, forcing tree search to approximate aggressively or degrade toward exhaustive scan.
Locality-Sensitive Hashing (LSH)

Uses hash functions designed so that collision probability is directly proportional to vector similarity:
$P[h(u) = h(v)] = \text{sim}(u, v)$
During search, query point $q$ is hashed into multiple hash buckets; only items sharing buckets with $q$ are evaluated.
Inverted File and Quantization (IVF-PQ)

The space is partitioned into $C$ Voronoi cells using $k$ -means centroids. Each vector is assigned to its nearest centroid (an Inverted File list, or IVF).

At query time, $q$ is compared only to the $C$ centroids. The algorithm selects the closest $n_{\text{probe}}$ centroids and inspects only the vectors residing in those specific lists. Vectors within lists are compressed via Product Quantization (PQ), splitting vectors into sub-vectors and estimating distances through lookup tables (Asymmetric Distance Computation).
Points are vertices in a directed graph; edges connect spatial neighbors.

Search operates as a greedy best-first traversal. Starting at an entry node, the algorithm evaluates distances to all outgoing neighbors of the current node, hopping to whichever neighbor is closest to $q$ . Traversal halts when local greedy steps no longer reduce the distance to $q$ within a candidate priority queue (beam search).

TIP
Graph-based methods achieve higher recall at lower latency than inverted files, but require significant index build time ( $\mathcal{O}(N \log N)$ distance computations) and hold substantial memory overhead for adjacency lists.

The power-law scaling of the proximity graph routing in NSW, however, causes extreme performance degradation in case of low dimensional or clustered data, which is why the Hierarchical Navigable Small World (Hierarchical NSW, HNSW) comes into play.

Hierarchical NSW#

The paper proposed the Hierarchical Navigable Small World (Hierarchical NSW, HNSW), a new fully graph based incremental K-ANNS structure, which can offer a much better logarithmic complexity scaling.

The idea of Hierarchical NSW algorithm is to separate the links according to their length scale into different layers and then search in a multilayer graph.

In such structure the search starts from the upper layer which has only the longest links (the “zoom-in” phase). The algorithm greedily traverses through the elements from the upper layer until a local minimum is reached. After that, the search switches to the lower layer (which has shorter links), restarts from the element which was the local minimum in the previous layer and the process repeats.

Illustration of the Hierarchical NSW idea. The search starts from an element from the top layer (shown red). Red arrows show direction of the greedy algorithm from the entry point to the query (shown green).

Constructing the Hierarchical Layers#

When a vector is inserted, the algorithm assigns it a ceiling layer index $l \in \{0, 1, 2, \dots\}$ . For example, if an element receives level $l = 2$ , it exists in Layer 0, Layer 1, and Layer 2. Every single vector exists at Layer 0 (the ground floor, which contains 100% of the dataset). Higher layers contain progressively smaller subsets of vectors.

Within any given layer, points are connected only to their spatial neighbors relative to the points present in that layer. To ensure higher layers become exponentially sparser, the level $l$ is drawn from an exponential distribution controlled by a scale parameter $m_L$ :

l = \lfloor -\ln(\text{uniform}(0, 1)) \cdot m_L \rfloor

where $m_L \approx \frac{1}{\ln(M)}$ , and $M$ is the target number of outgoing links per node. The probability behavior under this setup is such that the probability that a point reaches layer $l$ is $P(\text{level} \ge l) = e^{-l / m_L} \approx M^{-l}$ . If $M = 16$ , for example, roughly $1$ in every $16$ vectors reaches Layer 1, $1$ in every $256$ reaches Layer 2, and so on. The result is that the total number of layers scales as $\mathcal{O}(\log N)$ , keeping the index compact and preventing top layers from becoming cluttered.

The search procedure is an iterative greedy search starting from the top layer and finishing at the zero layer.

Yahoo Vespa#

Long before “vector database” became industry parlance, large-scale production search engines had already implemented aspects of vector database. Yahoo’s Vespa engine, which originated inside Norwegian enterprise search firm FAST Search & Transfer before being acquired and eventually open-sourced in 2017, had integrated tensor evaluation and vector search alongside traditional inverted indexes.

RAG & Vector Database

https://blogs.openml.io/posts/rag/

Author

OpenML Blogs

Published at

2026-11-07

License

CC BY-NC-SA 4.0

Agent Workflow

AI Agent - An Overview

1

The Graph Standard: HNSW

Approximate Nearest Neighbor Search (KKK-ANNS) Algorithm

How KKK-ANNS Works Under the Hood

Hierarchical NSW

Constructing the Hierarchical Layers

2

Yahoo Vespa

The Graph Standard: HNSW#

Approximate Nearest Neighbor Search (KKK-ANNS) Algorithm#

How KKK-ANNS Works Under the Hood#

Hierarchical NSW#

Constructing the Hierarchical Layers#

Yahoo Vespa#

Approximate Nearest Neighbor Search ( $K$ -ANNS) Algorithm#

How $K$ -ANNS Works Under the Hood#