Vector Search

Definition

Vector search takes a query vector and returns the stored vectors nearest to it under a distance or similarity metric — its k nearest neighbours. Every item you want to search over (a sentence, an image, a product, a user) is first turned into an embedding: a fixed-length list of numbers, often a few hundred to a couple of thousand of them, that places the item as a point in a high-dimensional space. Search then means geometry: given the query's point, find the handful of stored points closest to it and return the items they came from.

That single primitive — nearest neighbours of a query vector — is what sits underneath semantic search, the retrieval step of retrieval-augmented generation, recommendation ("users near this user"), and near-duplicate detection. Semantic search is the idea of retrieving by meaning; vector search is the mechanism that makes it fast, and the rest of this page is about that mechanism: which distance metric to measure closeness with, why you almost never compare against every vector, and what the index that avoids doing so gets wrong.

How It Works

Closeness has to be defined before it can be searched, and three metrics dominate. Cosine similarity is the cosine of the angle between two vectors, a·b / (‖a‖‖b‖); it ranges from 1 (same direction, treated as most similar) through 0 (orthogonal) to −1 (opposite), and it ignores length entirely, comparing only direction. Dot product a·b is cosine multiplied back by the two lengths, so it rewards longer vectors as well as aligned ones — useful when magnitude itself carries signal, and the metric most embedding-search indexes compute natively. Euclidean (L2) distance is the straight-line gap ‖a − b‖. These are not as different as they look: for two unit-length vectors, ‖a − b‖² = ‖a‖² + ‖b‖² − 2·a·b = 2 − 2·cos(a, b), so once vectors are normalised to length 1, Euclidean, dot product and cosine all produce the same ranking. That identity is why the standard move is to normalise every vector once and stop worrying about which metric to pick.

With a metric chosen, the honest way to answer a query is to measure it against every stored vector and keep the closest — an exact, brute-force scan. Its cost is one dot product per vector, and a dot product over a d-dimensional vector is d multiply-add operations. Take a corpus of 10 million embeddings at 768 dimensions (768 is a common embedding width, a convention of the model, not a law): a single query costs 10,000,000 × 768 ≈ 7.68 billion multiply-adds. That is exact and simple, and it is far too slow for an interactive search box the moment the corpus grows — the cost is linear in the number of vectors, so ten times more data is ten times the wait.

The escape is to stop insisting on the true nearest neighbours and accept the almost-always nearest ones. This is approximate nearest-neighbour (ANN) search, and it changes the cost curve rather than shaving a constant off it. The dominant ANN index is HNSW — Hierarchical Navigable Small World graphs, from Malkov and Yashunin's 2016 paper. HNSW connects each vector to a few of its near neighbours in a layered proximity graph; a query enters at the top, sparse layer and greedily hops toward whichever neighbour is closest to the query, descending into denser layers as it homes in. Because each hop roughly halves the remaining distance, a query touches on the order of the logarithm of the corpus size — about log₂(10,000,000) ≈ 23 steps of local work instead of 10 million comparisons. That is the recall-versus-speed trade the whole field turns on: you give up a few percent of recall and buy queries that are orders of magnitude faster, and a search-effort knob (how many candidates to keep in flight) lets you slide along that curve per query.

Memory is the other cost, and it is often the binding one. Those 10 million 768-dimensional vectors, stored as 32-bit floats, occupy 10,000,000 × 768 × 4 bytes ≈ 30 GB before the index's own graph links are added on top — which is why quantisation (storing each number in one byte instead of four, cutting the footprint about 4× to roughly 7.7 GB) is a standard companion to ANN rather than an afterthought. A vector database — a system such as FAISS (Meta's open-source similarity-search library), or a managed service built around one — is what packages the metric, the ANN index and this memory layout together and keeps them consistent as vectors are added and removed.

Types

The first split is exact versus approximate, and it is a real one: exact search guarantees the true neighbours at linear cost, approximate search trades a guarantee for speed. Within approximate search, the recognised index families differ in the data structure they use to avoid a full scan:

• Graph-based (HNSW, NSG): navigable proximity graphs walked greedily toward the query. The current default for high-recall, in-memory search, and what most vector databases use out of the box.
• Quantisation-based (product quantisation, IVF-PQ): compress vectors into short codes so many more fit in memory and distances are computed on the codes. Trades some accuracy for a much smaller footprint, so it scales to the largest corpora.
• Tree-based (k-d trees, Annoy's random-projection forests): recursively partition the space and search only the promising branches. Effective in low dimensions, but the partitions lose their edge as dimensionality climbs.
• Hash-based (locality-sensitive hashing): hash functions engineered so that nearby vectors collide into the same bucket, turning search into a bucket lookup.

These are engineering families, not a taxonomy someone invented to fill a heading — a practitioner picks among "HNSW, IVF-PQ or LSH" by name. The partition-based idea (IVF: bucket vectors into cells, scan only the cells nearest the query) is the one worked through in the code example below because it is the simplest to write from scratch.

Real-World Applications

The application driving vector search into mainstream infrastructure is the retrieval stage of retrieval-augmented generation: before a language model answers, vector search pulls the handful of passages whose embeddings are nearest the question's embedding and hands them to the model as context. This is why vector databases became standard equipment for AI assistants and documentation chatbots — the model is only as grounded as the neighbours the index returns.

Recommendation is the older, larger deployment. "Find items similar to this one" and "find users near this user" are literally nearest-neighbour queries over learned embeddings, and large-scale recommenders at streaming and e-commerce companies run ANN indexes over hundreds of millions of item vectors to produce candidate lists in milliseconds. The same primitive powers reverse-image and visual-similarity search (nearest neighbours of an image's embedding), audio and song matching, and near-duplicate detection and deduplication, where two documents or images being "the same" means their vectors sit within a small distance of each other. In every case the work is identical — nearest neighbours of a query vector — and only the embedding model upstream changes.

Key Concepts

• Recall@k: the fraction of the true top-k neighbours an approximate index actually returns; the standard yardstick for how much accuracy an ANN index has traded for speed. A recall@10 of 0.95 means it found 9.5 of the 10 items an exact scan would have.
• Search-effort parameter: the per-query knob (ef in HNSW, nprobe in IVF) that sets how many candidates the index examines. Turning it up raises recall and query time together — this is the tunable point on the recall-versus-speed curve.
• Normalisation: scaling every vector to length 1. Once done, cosine, dot product and Euclidean rank identically, which removes a whole class of metric-mismatch bugs.
• Quantisation: storing each vector component in fewer bits (int8, or product-quantisation codes) to shrink the index, accepting a small drop in recall for a large drop in memory.
• Curse of dimensionality: in very high-dimensional spaces distances between points concentrate, so "nearest" becomes weakly defined — the reason ANN works on structured embeddings but not on unstructured high-dimensional noise. See dimensionality reduction for the counter-pressure.

Challenges

The defining catch is that approximate search is allowed to be wrong. An ANN index returns approximate neighbours, so its recall is below 100% by design: it can miss the genuine nearest vector. When a retrieval system returns nothing useful, or the obviously-relevant document that a keyword search would have nailed, the instinct is to blame the data or the embedding model — but the cause is often the index skipping the region the answer lived in. The fix is frequently just raising the search-effort parameter (ef or nprobe) and re-checking recall@k against an exact scan on a sample of queries; if recall was 0.6 and the missing document reappears at 0.95, the index was the bug. This makes recall@k a metric to monitor in production, not just quote once at launch.

The quietest failure is metric mismatch. If vectors are not unit-normalised, ranking by cosine and ranking by dot product give different answers, because dot product also multiplies in each vector's length. An index configured for one metric while the vectors were built for the other returns a plausible-looking, confidently-scored, wrong ranking — nothing errors, results just get subtly worse. The worked example below makes this concrete: on vectors with varied lengths, the top-10 by dot product and the top-10 by cosine overlap in only 1 of 10 items. Normalising up front is the standard defence precisely because it collapses the two metrics into one.

Beyond correctness, memory is usually the ceiling before compute is. High-recall graph indexes like HNSW keep the vectors and their graph links resident in RAM, so the 30 GB of raw floats above becomes the floor of a larger footprint — which is why quantisation and on-disk indexes exist, each reintroducing a small recall cost. And filtered search — "nearest neighbours, but only among in-stock products from this seller" — fights the index: a metadata filter can eliminate most of the very neighbours the graph would have walked through, so the traversal has to work harder or fall back toward a scan, and naive filtering can quietly collapse recall. These are the trade-offs a vector database is trying to manage on your behalf, and the ones worth checking when its answers disappoint.

Code Example

The example builds an exact scan and a partition-based (IVF) approximate index over the same 50,000 vectors, then measures recall@10 at three search-effort settings — showing directly how scanning a larger slice of the corpus buys back recall. It closes on the metric-mismatch trap: the same query ranked by dot product versus cosine on un-normalised vectors.

import numpy as np

rng = np.random.default_rng(0)

# 50,000 unit-length vectors in 128 dimensions, drawn around 300 latent
# centres so the space has the neighbourhood structure real embeddings have.
# (Uniformly random points would not: in 128-D almost every pair is nearly
# equidistant, and no index can help.)
N, D, K = 50_000, 128, 300
centres = rng.standard_normal((K, D)).astype(np.float32)
labels  = rng.integers(0, K, N)
X = centres[labels] + 0.35 * rng.standard_normal((N, D)).astype(np.float32)
X /= np.linalg.norm(X, axis=1, keepdims=True)

unit = lambda v: v / np.linalg.norm(v)

# EXACT search: one dot product against every vector. On unit vectors the dot
# product IS cosine similarity, so this is N*D = 6,400,000 multiply-adds/query.
def exact_top10(q):
    return set(np.argsort(-(X @ q))[:10])

# APPROXIMATE search (IVF): carve the corpus into 200 cells around random
# centroids; at query time score only the `nprobe` nearest cells.
n_cells = 200
cen = X[rng.choice(N, n_cells, replace=False)]
cell_of = np.argmax(X @ cen.T, axis=1)
members = [np.where(cell_of == c)[0] for c in range(n_cells)]

def ivf_top10(q, nprobe):
    cells = np.argsort(-(cen @ q))[:nprobe]
    cand  = np.concatenate([members[c] for c in cells])
    return set(cand[np.argsort(-(X[cand] @ q))[:10]]), len(cand)

# A query lives on the same manifold as the documents: a latent centre + noise.
def query():
    c = centres[rng.integers(0, K)] + 0.35 * rng.standard_normal(D).astype(np.float32)
    return unit(c.astype(np.float32))

print("nprobe  recall@10  corpus scanned")
for nprobe in (1, 4, 16):
    r, s = [], []
    for _ in range(300):
        q = query()
        approx, n = ivf_top10(q, nprobe)
        r.append(len(exact_top10(q) & approx) / 10)
        s.append(n)
    print(f"  {nprobe:2d}      {np.mean(r):.2f}        {100*np.mean(s)/N:4.1f}%")

# METRIC MISMATCH: give the vectors varied lengths, then rank the SAME query by
# raw dot product vs cosine. They disagree almost completely.
q = query()
Y = X * rng.uniform(0.2, 5.0, size=(N, 1)).astype(np.float32)
dot_top = set(np.argsort(-(Y @ q))[:10])
cos_top = set(np.argsort(-((Y / np.linalg.norm(Y, axis=1, keepdims=True)) @ q))[:10])
print("dot-product vs cosine top-10 overlap:", len(dot_top & cos_top), "of 10")

Running it prints:

nprobe  recall@10  corpus scanned
   1      0.68         0.6%
   4      0.91         2.2%
  16      0.99         8.1%
dot-product vs cosine top-10 overlap: 1 of 10

The recall column is the whole story of ANN in three lines. Scanning just 2.2% of the corpus (nprobe=4) already recovers 91% of the true top-10; pushing to 8.1% reaches 99%. You are choosing, per query, how much of the exact answer to buy — and even the cheapest setting, touching under 1% of the data, gets two-thirds of it right. The last line is the metric-mismatch warning made real: the moment vector lengths vary, dot product and cosine agree on only 1 of the 10 nearest items, so shipping one metric while your vectors assume the other silently returns a different ranking. Swap these hand-rolled pieces for HNSW inside a vector database over real embeddings, and this is production nearest-neighbour search.