Vector Search

Published September 3, 2026 · Information Retrieval & Computational Geometry

Vector search (also termed dense retrieval or semantic similarity search) is an algorithmic retrieval paradigm that queries and ranks documents based on the geometric distance between dense embedding representations in a continuous multi-dimensional metric space. Unlike classical lexical search engines that match literal character tokens, vector search discovers contextually relevant passages based on latent conceptual alignment.

1. Problem Formulation: Exact vs. Approximate Nearest Neighbors

Given a dataset of $N$ vectors $\mathcal{S} = \{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_N\} \subset \mathbb{R}^d$ and an input query vector $\mathbf{q} \in \mathbb{R}^d$, the exact $k$-Nearest Neighbor ($k$-NN) problem identifies a subset $\mathcal{R} \subseteq \mathcal{S}$ of size $k$ satisfying:

$$\mathcal{R} = \arg \min_{\mathcal{R}' \subseteq \mathcal{S}, |\mathcal{R}'|=k} \sum_{\mathbf{v} \in \mathcal{R}'} \text{dist}(\mathbf{q}, \mathbf{v})$$

Brute-force exact search computes the distance between $\mathbf{q}$ and every vector in $\mathcal{S}$, resulting in an operational complexity of $\mathcal{O}(N \cdot d)$. For production corpora containing millions to billions of high-dimensional vectors ($d \in [768, 3072]$), exact search imposes unacceptable search latencies exceeding hundreds of milliseconds.

Vector search systems circumvent this bottleneck using Approximate Nearest Neighbor (ANN) algorithms. ANN accepts a negligible loss in theoretical recall (e.g. retrieving 98% of the true top-$k$ nearest neighbors) in exchange for sub-linear logarithmic query complexity $\mathcal{O}(\log N)$.

2. Approximate Nearest Neighbor (ANN) Indexing Algorithms

Hierarchical Navigable Small World (HNSW)

HNSW constructs a multi-layer graph where nodes represent embedding vectors and edges represent proximity relationships [1]. The structure generalizes the concept of skip lists to geometric graphs:

Upper Layers: Contain sparse subsets of vectors with long-range geometric links, allowing the search algorithm to traverse large Euclidean distances across the manifold in few hops.
Bottom Layer (Layer 0): Contains all vectors interconnected with dense, localized links, supporting fine-grained greedy local routing.

Search begins at a fixed entry point in the highest layer, performing greedy traversal until reaching a local minimum, then dropping to the corresponding node in the layer below. HNSW achieves high empirical recall and sub-millisecond query latencies, though it requires substantial RAM to store graph adjacency lists alongside vector buffers.

Inverted File & Product Quantization (IVF-PQ)

When dataset scale renders in-memory graph storage cost-prohibitive, systems deploy quantization methods [2]:

Inverted File (IVF): Partitions the vector space into $K$ Voronoi cells using $k$-means clustering. Queries compute distances only to the nearest centroid clusters (nprobe), pruning 95% to 99% of search space candidates.
Product Quantization (PQ): Decomposes a $d$-dimensional vector into $M$ orthogonal sub-vectors of dimension $d/M$. Each sub-vector is mapped to its nearest centroid codebook index (typically 256 centroids per sub-space, requiring 1 byte):

$$\min_{\mathcal{C}_1, \dots, \mathcal{C}_M} \sum_{\mathbf{x}} \sum_{m=1}^M \|\mathbf{x}^{(m)} - q(\mathbf{x}^{(m)})\|_2^2$$

A 1536-dimensional float32 vector (6,144 bytes) is compressed into 64 bytes, enabling billions of vectors to reside entirely within RAM cache.

Disk-Backed Graph Architectures (DiskANN)

DiskANN eliminates the RAM bottleneck by storing compressed vectors in memory for candidate routing while streaming full-precision vectors from solid-state drives (NVMe SSDs) during final reranking [3]. Using single-layer compressed Vamana graphs, DiskANN scales to billions of vectors per node at 10% of the hardware cost of pure-RAM HNSW clusters.

3. Distance Metrics & Space Geometry

The choice of distance metric aligns with the training loss function of the underlying embedding model:

Cosine Distance: $1 - \cos(\theta) = 1 - \frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\|_2 \|\mathbf{v}\|_2}$. Preferred for text corpora where document token lengths vary widely.
Dot Product (Inner Product): $-\langle \mathbf{u}, \mathbf{v} \rangle$. Computationally optimal when vectors are $L_2$-normalized prior to ingestion, as $\|\mathbf{u}\| = \|\mathbf{v}\| = 1$ makes dot product monotonically equivalent to cosine similarity and Euclidean distance.
Euclidean Distance ($L_2$): $\|\mathbf{u} - \mathbf{v}\|_2$. Standard for spatial coordinates, image representations, and unnormalized clustering models.

4. Hybrid Retrieval & Reciprocal Rank Fusion

Pure vector search exhibits documented failure modes on exact keywords, alphanumeric identifiers, part numbers, and proper nouns (e.g. searching "CVE-2024-38077" often retrieves general cybersecurity passages rather than the exact vulnerability record). State-of-the-art production search combines dense vector retrieval with sparse lexical retrieval (BM25) [4].

Rankings are unified using Reciprocal Rank Fusion (RRF), which scores candidates without requiring score calibration across disparate metrics:

$$\text{RRF}(d) = \sum_{m \in M} \frac{1}{k + r_m(d)}$$

where $M = \{\text{dense}, \text{sparse}\}$, $r_m(d)$ is the ordinal rank of document $d$ in retrieval channel $m$, and $k$ is a smoothing constant (typically $k=60$). A cross-encoder re-ranker then scores the top 50 fused candidates to maximize precision.

5. Systems Constraints: Memory Footprint & Metadata Filtering

Production vector search introduces distinct database design challenges:

Pre-filtering vs. Post-filtering: Filtering by user permissions, tenant IDs, or dates before graph traversal (pre-filtering) can disconnect the graph and trap greedy routing in dead ends. Filtering after retrieval (post-filtering) risks returning fewer than $k$ items if top candidates fail the filter. Modern vector databases employ single-stage iterative graph filtering to dynamically route around invalid nodes during traversal.
CRUD Operations: Graph structures like HNSW do not support trivial vector deletions without triggering expensive edge re-wiring or leaving orphan nodes, necessitating tombstone flags and background compaction cycles.

References

[1] Y. A. Malkov and D. A. Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 42, no. 4, pp. 824–836, 2018. https://arxiv.org/abs/1603.09320
[2] H. Jégou, M. Douze, and C. Schmid, "Product Quantization for Nearest Neighbor Search," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, pp. 117–128, 2011.
[3] S. Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy, and R. Kadekodi, "DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node," in NeurIPS, 2019, pp. 13766–13776.
[4] G. V. Cormack, C. L. A. Clarke, and S. Büttcher, "Reciprocal Rank Fusion out上下performs individual retrieval methods," in SIGIR, 2009, pp. 758–759.
[5] R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simcha, F. Chern, and S. Kumar, "Accelerating Large-Scale Inference with Anisotropic Vector Quantization," in ICML, 2020, pp. 3887–3896. https://arxiv.org/abs/1908.10396