Embeddings and similarity search

Sparse embeddings (e.g., TF-IDF, BM25, SPLADE) are high-dimensional vectors where most entries are zero and dimensions map to vocabulary terms, giving strong exact lexical matching and interpretability. Dense embeddings (e.g., from transformer encoders) are low-dimensional continuous vectors capturing semantic similarity but can miss rare exact terms. Hybrid retrieval combines both, typically fusing scores with weighted sum or Reciprocal Rank Fusion, to capture both keyword precision and semantic recall.

Cosine similarity measures the angle between vectors, ignoring magnitude, which makes it robust to differences in vector norm that often correlate with token count or frequency rather than meaning. Many embedding models are trained with cosine/dot-product objectives, so cosine aligns with the learned geometry. For L2-normalized vectors, cosine similarity and Euclidean distance produce equivalent rankings, since one is a monotonic function of the other.

HNSW builds a multi-layer proximity graph where upper layers are sparse long-range links and lower layers are dense local links, like a skip list over a navigable small-world graph. Search starts at the top layer's entry point, greedily moves to the closest neighbor, then descends layers, refining the candidate set with a priority queue of size efSearch. This yields logarithmic-scale search complexity with high recall, trading memory (storing graph edges) for speed.

Product Quantization splits each vector into m subvectors and learns a separate k-means codebook (typically 256 centroids) per subspace, encoding each subvector as a 1-byte centroid index. A D-dimensional float32 vector thus compresses to m bytes, often a 10-50x reduction. Distances are approximated via precomputed lookup tables (asymmetric distance computation), enabling fast scoring at the cost of quantization error.

IVF accelerates search by partitioning the vector space with k-means into nlist Voronoi cells and assigning each vector to its nearest centroid, so queries only scan a few cells instead of the whole dataset. At query time, nprobe controls how many of the closest cells are searched: higher nprobe increases recall but reduces speed. It is commonly combined with PQ (IVFPQ) to also compress the stored residuals.

Embedding spaces are model-specific; different models or even versions place the same concept at different coordinates, so vectors from two models are not comparable and similarity scores become meaningless. Query and document vectors must live in the same learned space for nearest-neighbor distances to reflect semantic relatedness. Changing the model requires re-embedding the entire corpus, not just new queries.

A bi-encoder encodes the query and each document independently into fixed vectors, enabling precomputation and fast ANN retrieval but losing fine-grained query-document interaction. A cross-encoder feeds the query and document together through the model and outputs a relevance score, capturing rich interactions for much higher accuracy but at high cost since nothing can be precomputed. The standard pattern is bi-encoder retrieval followed by cross-encoder reranking of the top-k.

As dimensionality grows, distances between points concentrate so the ratio between nearest and farthest neighbor approaches 1, making it hard to distinguish true neighbors and degrading exact and approximate search. Volume grows exponentially, so data becomes sparse and tree-based partitioning indexes lose their pruning power. Learned embeddings mitigate this by mapping data onto a lower-dimensional semantic manifold where meaningful structure is preserved.

Matryoshka embeddings are trained so that meaningful information is front-loaded into the leading dimensions, meaning a prefix of the full vector (e.g., the first 256 of 1536 dims) is itself a usable lower-quality embedding. This lets you truncate vectors to trade accuracy for lower storage and faster search without retraining or re-embedding. A common pattern is a coarse search on truncated vectors followed by reranking with the full-dimensional vectors.

IndexFlatL2 does exact brute-force search using squared Euclidean distance, while IndexFlatIP uses inner (dot) product. For cosine similarity you L2-normalize all vectors and then use IndexFlatIP, because the dot product of unit vectors equals their cosine. Both 'Flat' indexes are exact and have no training step, serving as accuracy baselines for approximate indexes.

import faiss, numpy as np
faiss.normalize_L2(xb)   # in-place L2 normalize
index = faiss.IndexFlatIP(d)
index.add(xb)
faiss.normalize_L2(xq)
scores, ids = index.search(xq, k)  # scores ~ cosine

ANN indexes deliberately sacrifice exactness for speed, so tuning parameters (efSearch in HNSW, nprobe in IVF) lets you slide along a recall-latency curve: more exploration yields higher recall but higher latency and CPU. The right operating point depends on the application's tolerance for missing relevant results versus its latency SLA. You measure this with recall@k against a brute-force ground truth and choose parameters that meet the SLA at acceptable recall.

A reranker (usually a cross-encoder or LLM-based scorer) re-scores the top-k ANN candidates with deeper query-document interaction, sharply improving precision at the top ranks that the LLM actually reads. Simply retrieving more candidates increases recall but floods the context with noise and exceeds token budgets, hurting answer quality. The pattern is high-recall cheap retrieval, then high-precision expensive reranking on a small candidate set.

Chunk size controls a granularity trade-off: chunks that are too large dilute the embedding with multiple topics and hurt precision, while chunks that are too small lose context needed for relevance and answers. Overlapping windows reduce information loss at boundaries, and semantic or structure-aware chunking (by sections/sentences) keeps coherent units together. Optimal chunking is corpus- and model-dependent and should be tuned against retrieval metrics.

Anisotropy means the embeddings occupy a narrow cone in the vector space rather than spreading uniformly, so even unrelated items have high cosine similarity, compressing the usable similarity range. This 'representation degeneration' is common in raw transformer outputs and reduces discriminative power. Mitigations include whitening, mean-centering, contrastive fine-tuning (e.g., SimCSE), or normalization that flattens the dominant directions.

Dot product is sensitive to both angle and magnitude, so it can be dominated by longer vectors and is used when magnitude carries signal (e.g., some MIPS setups). Cosine measures only direction, normalizing out magnitude, which is typical for semantic similarity. Euclidean (L2) measures absolute distance; on L2-normalized vectors it is rank-equivalent to cosine (and to negative dot product), so the choice mostly matters when vectors are not normalized.

MIPS finds the vector maximizing the inner product with a query, which is the natural objective for many recommendation and retrieval models. Inner product is not a metric (it violates the triangle inequality and a vector is not closest to itself), so metric-space structures like KD-trees and ball-trees that rely on those properties don't apply directly. Common solutions transform MIPS into nearest-neighbor search via augmentation/normalization or use graph indexes like HNSW that work with arbitrary inner-product scores.

Use ranking metrics on a labeled query-document set: recall@k and MRR/MAP for whether relevant items are retrieved and ranked high, and nDCG when relevance is graded. Standardized benchmarks like MTEB (and BEIR for retrieval) give cross-domain comparisons, but in-domain evaluation on your own data matters most. Also consider operational factors: dimensionality, latency, cost, and multilingual or domain coverage.

Contrastive learning trains embeddings to pull semantically related (positive) pairs together and push unrelated (negative) pairs apart in vector space, typically via InfoNCE loss with in-batch negatives. This directly shapes the geometry so that similarity (cosine/dot) reflects semantic relatedness, which is exactly what retrieval needs. Hard negatives and large batch sizes substantially improve the discriminative quality of the learned space.

Easy negatives are trivially separable and provide little gradient signal, whereas hard negatives are semantically close-but-incorrect examples that force the model to learn fine distinctions and sharpen decision boundaries. They are commonly mined by retrieving top-ranked non-relevant documents with a baseline retriever (BM25 or an earlier embedding model) for each query. Care is needed to filter false negatives, since unlabeled relevant items mined as negatives can poison training.

Binary quantization maps each dimension to a single bit (e.g., sign of the value), shrinking storage by ~32x versus float32 and letting similarity be computed with extremely fast Hamming distance. It loses precision, so the standard pattern is a fast binary first-stage search to fetch a large candidate set, then rescoring those candidates with the original float (or int8) vectors. This delivers most of the speed/memory win while recovering recall via rescoring.

Instead of compressing a document into one vector, ColBERT stores a contextual embedding per token and scores a query-document pair via MaxSim: for each query token it takes the max similarity over all document tokens and sums these. This 'late interaction' retains fine-grained token-level matching, giving accuracy near cross-encoders while remaining precomputable and indexable. The cost is much larger storage and a specialized index, since you keep many vectors per document.

Studies show LLMs attend most strongly to information at the beginning and end of their context, with relevance dropping for facts buried in the middle of a long context. So even with good retrieval, placing the most relevant chunks in the middle of a large prompt can hurt answers. Practical mitigations include reranking to surface fewer, higher-quality chunks and ordering the best evidence at the start or end of the context.

Reducing dimensions lowers storage and speeds up distance computations and indexing, and can remove noisy directions that dominate raw transformer outputs. The risk is discarding directions that carry discriminative signal, degrading recall, especially if reduction is fit on a non-representative sample. Matryoshka embeddings are a built-in alternative since they support truncation without a separate fitted projection.

In symmetric search, queries and documents are similar in form and length (e.g., duplicate-question detection), so a single encoder treating both the same works well. In asymmetric search, short queries are matched against long passages (typical RAG), so models are often trained with query/passage prefixes or dual objectives to bridge the length/style gap. Choosing or prompting the embedding model to match your task's symmetry materially affects retrieval quality.

These models prepend task-specific instructions or role prefixes like 'query:' and 'passage:' (or natural-language task descriptions) so the same backbone produces embeddings tailored to the retrieval intent. This helps asymmetric search and lets one model serve multiple tasks by changing the instruction rather than retraining. Using the exact prefixes the model was trained with is critical, since omitting or mismatching them degrades quality.

# E5-style usage
q = model.encode('query: how to reset password')
d = model.encode('passage: To reset your password, go to settings...')

RRF combines multiple ranked lists by summing 1/(k + rank) for each item across lists (k often ~60), rewarding items ranked high in any source. It needs only ranks, not calibrated scores, so it cleanly merges incomparable scorers like BM25 and dense cosine without score normalization. This simplicity and robustness make it a default fusion method for hybrid lexical+semantic retrieval.

def rrf(rank_lists, k=60):
    scores = {}
    for lst in rank_lists:
        for rank, doc in enumerate(lst):
            scores[doc] = scores.get(doc, 0) + 1/(k + rank)
    return sorted(scores, key=scores.get, reverse=True)

Graph indexes like HNSW support inserts but handle deletes poorly, often using soft-delete tombstones that bloat the graph and require periodic rebuilds to reclaim quality and space. Updates usually mean delete-plus-reinsert, and bulk re-embedding is needed when the model changes. Production systems address this with segment-based architectures (immutable segments + background merges/compaction) and versioned reindexing to avoid downtime.

Pre-filtering can leave too few candidates in the graph region, breaking ANN navigability, while post-filtering may discard most retrieved neighbors and miss valid matches, hurting recall. Highly selective filters are especially problematic because the relevant subset is sparse in the index. Modern systems use filter-aware/hybrid approaches (e.g., HNSW with inline filtering or partitioned indexes) to keep recall high under constraints.

Normalizing to unit length makes the dot product equal the cosine similarity, so inner-product indexes directly yield cosine rankings and similarity scores fall in a consistent [-1, 1] range. It removes magnitude effects (often tied to length/frequency) that would otherwise distort comparisons, and it stabilizes thresholds across the corpus. Many ANN libraries assume normalized vectors when configured for cosine.

Recall@k for an ANN index is the fraction of the true top-k nearest neighbors that the approximate search actually returns in its top-k, measuring fidelity to exact search rather than human relevance. Ground truth is computed with exact brute-force (flat) search over the same vectors and metric. It is the key metric for tuning ANN parameters (efSearch, nprobe) against latency.

HyDE (Hypothetical Document Embeddings) prompts an LLM to generate a hypothetical answer/document for the query, then embeds that richer text instead of (or alongside) the short query to retrieve real documents. This bridges the lexical/semantic gap between terse queries and verbose passages, improving asymmetric retrieval. The trade-off is added LLM latency/cost and the risk of hallucinated content steering retrieval off-topic.

Models like CLIP are trained contrastively to map images and text into a shared embedding space so that matching image-text pairs have high similarity. This lets you search images with text queries (and vice versa) using ordinary cosine/dot-product nearest-neighbor search in the joint space. The key requirement is that all modalities are encoded into the same aligned space, typically by the same trained model family.

High dimensions increase memory footprint and bandwidth (a 3072-dim float32 vector is ~12 KB), raise per-comparison compute cost, and inflate index build time and RAM. They can also amplify distance concentration with limited extra signal beyond a point. Teams mitigate with Matryoshka truncation, quantization (int8/binary/PQ), or PCA, balancing recall against cost.

Off-the-shelf general models are best when your domain language overlaps common web text and you lack labeled pairs; they avoid training cost and overfitting. Fine-tuning (typically contrastive with in-domain query-document pairs and hard negatives) pays off for specialized jargon, proprietary terminology, or when benchmark recall on your own data is poor. The decision should be driven by measured in-domain retrieval metrics, not assumptions, and weigh the cost of labeling and maintenance.