Technical Deep Dives

Vector Databases and Embedding Search

A deep dive into vector databases, embedding spaces, similarity search algorithms, and how they power modern AI applications from RAG to recommendation systems.

Gabriele Masetti · 2026-08-17

Why nearest-neighbor search needs its own database

An embedding is a vector that a model produces so that semantic similarity becomes geometric proximity. Two sentences that mean similar things land near each other in the vector space; two unrelated ones land far apart. Once you have millions of these vectors, the only useful operation is: given a query vector, find its nearest neighbors under some distance function. That sounds like a job for an index, and for small datasets a brute-force scan works fine — compare the query against every stored vector and sort.

The trouble is that exact nearest-neighbor search is linear in the number of vectors and linear in dimensionality, and modern embedding models produce vectors with hundreds to thousands of dimensions. OpenAI's text-embedding-3-small defaults to 1536 dimensions, and text-embedding-3-large defaults to 3072 (both models let you truncate via a dimensions parameter, trading a bit of retrieval quality for storage).

At tens of millions of vectors, brute-force comparison against every candidate stops being feasible for interactive latency budgets. This is the problem vector databases and approximate nearest neighbor (ANN) libraries exist to solve: return neighbors that are almost certainly correct, in milliseconds, by refusing to look at every vector.

The "approximate" in ANN is the central design tradeoff of this entire field. Every index structure below buys speed by accepting some probability of missing the true nearest neighbor. The metric for how often it succeeds is recall@k — the fraction of true top-k neighbors the index actually returns — and every practical system exposes a knob that trades recall against latency and memory. Understanding that knob, and where it lives in each algorithm, is most of what you need to operate these systems well.

Distance metrics: cosine, dot product, and Euclidean

Before indexing, you need a similarity function. Three dominate:

• Cosine similarity measures the angle between two vectors, ignoring magnitude. It's the default choice for text embeddings because it cares about direction (semantic content) rather than vector length.
• Dot product measures both direction and magnitude. It's cheaper to compute than cosine similarity because it skips the normalization step.
• Euclidean (L2) distance measures straight-line distance in the vector space.

These aren't three arbitrary options — they collapse into one when your vectors are normalized to unit length. OpenAI's embeddings are normalized this way, which is why their documentation notes that cosine similarity, dot product, and Euclidean distance produce identical rankings on their outputs; dot product is just the fastest to compute, so it's the practical default. If you use a model that doesn't normalize its output, the three metrics can disagree, and picking the wrong one measurably hurts retrieval quality.

This is a detail worth checking for any embedding model before you pick an index metric, because getting it wrong is a silent failure — search still returns results, just worse ones.

HNSW: navigating a small-world graph

The dominant ANN algorithm in production vector databases today is HNSW — Hierarchical Navigable Small World graphs — introduced by Yury Malkov and Dmitry Yashunin, with the definitive paper published in IEEE Transactions on Pattern Analysis and Machine Intelligence (vol. 42, issue 4, 2018), following an earlier arXiv preprint in 2016. HNSW is the index behind FAISS's IndexHNSWFlat, pgvector's hnsw index type, and the default or primary index in Weaviate, Qdrant, and Milvus.

The core idea is a multi-layer proximity graph. Each vector is a node, and nodes are connected to nearby nodes by edges — but instead of one flat graph, HNSW builds a hierarchy of graphs stacked on top of each other. Layer 0 at the bottom contains every vector.

Each layer above it contains a randomly-selected, exponentially shrinking subset of the vectors below — a vector's maximum layer is chosen randomly with an exponentially decaying probability distribution, so most vectors only exist in layer 0, a few climb to layer 1, fewer still to layer 2, and so on. This mirrors a skip list: sparse long-range shortcuts on top, dense local connections at the bottom.

A search starts at an entry point in the topmost layer and greedily walks toward the query vector, hopping to whichever neighbor is closer, until it can't improve within that layer. It then drops down one layer and repeats the greedy walk, using the previous layer's local optimum as its new starting point, all the way down to layer 0, where it does a wider best-first search over a candidate set to assemble the final top-k.

Because the upper layers act as coarse routing tables that get you to roughly the right neighborhood in a handful of hops, and the lower layers refine locally, search complexity scales logarithmically with the number of stored vectors — a property that lets HNSW stay fast well past the dataset sizes where naive graph search degrades.

Two build-time parameters control the recall/resource tradeoff: M, the number of edges maintained per node (higher M means denser connectivity, better recall, and more memory), and efConstruction, which controls how thorough the search is while inserting new nodes and thus how good the resulting graph structure is. At query time, efSearch controls the width of the candidate list kept during the layer-0 search — raise it and recall goes up while latency goes up with it.

This is the single most important tuning lever across every HNSW-based system: ef/efSearch is the recall-vs-latency dial you turn per query, while M and efConstruction are the recall-vs-memory-and-build-time dial you set once.

HNSW's weaknesses are the mirror of its strengths: the graph structure with its per-node edge lists is memory-hungry (uncompressed, expect memory on the order of a few times the raw vector size), and because it's an incrementally-built graph, deletions are awkward — most implementations mark nodes as tombstoned rather than truly remove them, and the graph benefits from periodic rebuilds under high churn.

IVF and product quantization: the FAISS approach

FAISS (Facebook AI Similarity Search), the library out of Meta's AI research group, popularized a different family of index: inverted file indexes (IVF). IVF first clusters the vector space using k-means into a set of partitions — conceptually like Voronoi cells, each with a centroid. At index time, every vector is assigned to its nearest centroid's list ("inverted file" is a nod to the same structure used in text search, where a term maps to a list of documents; here a centroid maps to a list of vectors).

At query time, rather than scanning everything, IVF computes distance to each centroid, picks the nprobe closest cells, and only scans vectors inside those cells. nprobe is the recall/latency knob here: scanning one cell is fast but risks missing neighbors that fell into an adjacent cell near the boundary; scanning many cells raises recall back toward exhaustive search at the cost of speed.

IVF alone controls how much of the dataset you touch. It says nothing about how much space each vector takes or how fast an individual distance computation is — that's where product quantization (PQ) comes in. PQ splits each high-dimensional vector into sub-vectors, and separately quantizes each sub-vector to the nearest of a small set of learned centroids (typically 256 per sub-space, so each sub-vector is representable in a single byte).

A 1536-dimension float32 vector that costs 6 KB raw can compress to well under 100 bytes as a PQ code — a lossy compression that trades exact distance computation for compact codes and fast approximate distance lookup via precomputed tables. Combined, IVFPQ is FAISS's workhorse for billion-scale search: cluster to narrow the candidate set, then quantize to make scanning that set cheap.

On a single GPU, this pipeline can return top-k results in microseconds per query, which is why FAISS remains the reference implementation cited in nearly every paper on large-scale retrieval infrastructure, even when production systems wrap it in a different index or ship their own reimplementation.

The quantization idea has since been generalized well beyond FAISS's original PQ. Qdrant implements scalar quantization, which converts float32 components to int8, cutting memory by roughly 75% while keeping search error typically under 1% — and as a side benefit, it lets the search loop use SIMD instructions built for 8-bit integers, which is faster on top of being smaller. Qdrant also implements binary quantization, compressing each vector component to a single bit — a 32x memory reduction that can yield roughly 40x faster search in benchmarks, at the cost of accuracy.

Binary quantization only works well on higher-dimensional embeddings (roughly 1024+ dimensions); it degrades badly on smaller embeddings because there isn't enough redundant information in the vector to survive being flattened to bits. All quantization schemes share the same operational pattern: quantized vectors are used to cheaply narrow a candidate set, and the original full-precision vectors are used to rescore the survivors — you get most of the memory and speed win without eating the full accuracy cost.

Choosing an index and a store

The practical decision isn't "HNSW or IVF" in the abstract — it's a set of tradeoffs against your workload:

• Recall vs. latency vs. memory is a triangle, not a line. HNSW tends to win on the recall/latency edge (best queries-per-second at a given recall target, particularly visible on public leaderboards like ann-benchmarks.com across datasets such as GloVe and SIFT), at the cost of memory footprint and slower, harder-to-parallelize index builds. IVF-family indexes build faster and use less memory, at some recall cost that's usually recoverable by raising nprobe.
• Write-heavy vs. read-heavy. If vectors are inserted continuously and rarely re-indexed in bulk, an index with fast incremental inserts and low rebuild pressure matters more than raw query throughput. IVFFlat's faster, cheaper builds suit this better than HNSW's slower, memory-heavier graph construction; pgvector explicitly documents this tradeoff between its two index types.
• Filtering. Real applications rarely want "nearest neighbors in the whole dataset" — they want nearest neighbors among documents owned by this user or within this date range. Pure vector indexes handle filtered search poorly if the filter is applied after the ANN search returns a candidate set (a highly selective filter can leave you with almost no results even though better matches exist elsewhere in the index). Systems differ in how they solve this: some do filtering during graph traversal, some maintain filtered sub-indexes, and some fall back to a wider unfiltered search plus post-filtering. It's a question worth asking directly when evaluating a store, because the answer materially affects both recall and latency under real filter predicates.
• Hybrid search — combining dense vector similarity with sparse lexical signals like BM25 — matters because embeddings are bad at exact-match cases (product SKUs, acronyms, rare proper nouns) where a keyword index is trivially correct. Weaviate ships native BM25 + vector fusion as a first-class feature rather than a bolt-on, which is a meaningful reason teams pick it when hybrid retrieval is a hard requirement rather than a nice-to-have.
• Operational model. Pinecone is a fully managed, serverless vector database designed to scale to billions of vectors with sub-100ms latency without the team running any infrastructure — you trade control and self-hosting for operational simplicity. Milvus is built for billion-scale search with multiple pluggable index types and multi-modal support, but is correspondingly heavier to operate yourself. Qdrant, written in Rust, has posted some of the lowest p50 latencies among purpose-built vector databases in independent benchmarking (on the order of single-digit milliseconds). Chroma is deliberately lightweight and developer-friendly, aimed at prototyping and small-to-medium applications rather than billion-vector, multi-tenant production loads. pgvector is the option for teams that already run PostgreSQL and want vector search as one more index type in the database they operate anyway, avoiding a second system entirely — its IVFFlat and HNSW index types map directly onto the tradeoffs above, and version 0.8.0 added iterative scanning to both, which lets a query keep expanding its search when a restrictive filter would otherwise starve it of results.

There's no universally correct choice. A team running retrieval-augmented generation over a few hundred thousand internal documents, with moderate write volume and a Postgres database already in production, gets more value from pgvector than from standing up a new managed service. A team building consumer search over hundreds of millions of product embeddings with unpredictable traffic spikes has a much stronger case for a managed, serverless system built for that scale. A team that needs hybrid keyword-plus-vector search as a core requirement, not an afterthought, should weight that capability as heavily as raw ANN benchmark numbers.

Scaling beyond a single node

At sufficient scale, the index itself stops being the only problem — distribution does. Sharding a vector index means partitioning vectors across nodes (commonly by hashing or by a coarse clustering step similar to IVF's centroids) and either querying all shards and merging results (scatter-gather) or routing queries to the shard likely to hold the answer.

Scatter-gather preserves recall better but multiplies query cost by the number of shards touched; routing is cheaper but reintroduces the risk of missing a true neighbor that landed on the "wrong" shard, which is the same recall/cost tradeoff that shows up inside a single IVF index, just moved up a layer of abstraction.

Replication for read throughput is comparatively simple — vector indexes are mostly read-heavy and embarrassingly parallel to serve once built — but keeping replicas consistent under continuous writes without stalling queries is where the real engineering effort in distributed vector databases like Milvus and Weaviate's cluster mode goes. And because rebuilding an HNSW graph from scratch is expensive at scale, production systems increasingly favor incremental index structures or a two-tier design: a fast, mutable buffer for recent writes searched exhaustively, periodically compacted into the main, immutable, quantized index — the same log-structured-merge pattern common in write-optimized databases, applied to vectors instead of rows.

The recurring tradeoff

Every layer of this stack — metric choice, HNSW's ef, IVF's nprobe, PQ's code size, binary quantization's bit-per-dimension — is the same knob wearing a different name: how much exhaustiveness are you willing to give up for speed and memory, and how much error can your downstream application tolerate. A recommendation system reranking a shortlist can tolerate more approximation than a legal-document retrieval system where a missed match is a real failure.

Getting vector search right is less about picking the "best" algorithm and more about identifying where your workload sits on that tradeoff, and choosing the index and store that let you tune it explicitly rather than discovering it by accident in production.