Vector Search and Embedding Retrieval
Embedding search basics, distance metrics, approximate indexes, recall tradeoffs, and retrieval evaluation.
Vector search maps items into an embedding space and retrieves neighbors under a distance or similarity function. It is useful when exact keyword matching is too brittle, but it is still an information-retrieval system. Retrieval quality needs measurement.
Similarity functions
For vectors $x$ and $y$, dot product is:
\[x^\top y = \sum_i x_i y_i\]Cosine similarity is:
\[\cos(x,y) = \frac{x^\top y}{\lVert x \rVert_2 \lVert y \rVert_2}\]If all vectors are normalized to unit length, maximizing cosine similarity is equivalent to maximizing dot product. Squared Euclidean distance between normalized vectors is also related:
\[\lVert x-y \rVert_2^2 = 2 - 2x^\top y\]This equivalence breaks when vectors are not normalized. Always record the metric and normalization policy used to build the index.
Exact and approximate search
Exact flat search compares the query against every vector. It has simple semantics and strong recall, but cost grows with corpus size:
\[O(Nd)\]where $N$ is vector count and $d$ is embedding dimension.
Approximate nearest neighbor indexes trade recall for latency and memory. Common families:
| Method | Main tradeoff |
|---|---|
| HNSW graph | high recall and fast search, more memory, expensive deletes |
| IVF | probes a subset of coarse clusters, tunable recall and latency |
| product quantization | lower memory, approximate distances, possible quality loss |
| flat GPU search | exact or near-exact behavior when memory and bandwidth fit |
HNSW exposes parameters such as graph degree and search depth. IVF exposes the number of lists and probes. These are product knobs, not only library settings.
Retrieval metrics
For top-k retrieval, recall@k is:
\[\text{recall@}k = \frac{|\text{relevant} \cap \text{retrieved}_k|}{|\text{relevant}|}\]Mean reciprocal rank rewards the first relevant result:
\[MRR = \frac{1}{Q}\sum_{q=1}^{Q}\frac{1}{rank_q}\]Use recall@k when downstream processing can inspect several candidates. Use MRR when the first hit dominates user value.
Failure modes
Embedding models encode the training objective, not truth. Nearness can reflect style, language, popularity, boilerplate, or source duplication rather than task relevance.
Chunking errors break retrieval. If chunks are too small, evidence loses context. If chunks are too large, embeddings smear multiple concepts together and retrieved context wastes model budget.
Approximate indexes can pass unit tests and still lose important neighbors. Recall must be measured against exact search on a representative sample.
Updates are not free. Some graph indexes do not support cheap deletion. Tombstones, rebuild windows, and versioned indexes need explicit design.
Practical checks
- Build a labeled query set before tuning index parameters.
- Compare ANN results against exact search for sampled queries.
- Track recall@k, latency, memory, index build time, and update lag.
- Test queries with synonyms, abbreviations, code identifiers, and negative cases.
- Keep embedding model version, chunker version, normalization policy, and index parameters with the index artifact.
- Evaluate retrieval separately from generation in RAG systems.
Design guidance
Start exact when the corpus fits. Move to approximate search only when measured latency or memory requires it. Treat every ANN knob as a quality-latency tradeoff and pin the choice with recall measurements.