What is similarity search and how does it work?

In this article

1. Before you start
2. Why interviewers ask this
3. Similarity search from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

Most modern retrieval systems, from semantic product search to a retrieval-augmented generation (RAG) pipeline, rest on this step, so interviewers use it to test whether you can reason about speed and accuracy together. A weak answer says "compute cosine similarity and sort." A strong answer says why that stops working at scale, what an index gives up in return, and how you would measure the loss. The question usually arrives as "find the ten most similar items among a hundred million," inside a machine learning system design round. The follow-up is nearly always the same: what is your recall, and how would you raise it?

Similarity search from first principles

Similarity search

Similarity search is a method that, given a query, returns the k stored items whose vectors are closest to the query's vector under a chosen distance, so that items with similar meaning or content come back first.

Approximate nearest-neighbour index

An approximate nearest-neighbour index is a data structure that organises vectors in advance so a query examines only a small part of them, returning most but not always all of the true nearest neighbours.

Index recall

Recall, for a search index, is the share of the true nearest neighbours, found by exact search, that the index also returns; a recall of 0.9 means nine of every ten true neighbours are found.

In plain words

Picture a pile of photographs on the floor and one photograph in your hand. You want the ten that look most like it. The slow way is to hold your photo against every other one. The fast way is to sort the pile into labelled boxes first. Then you look only in boxes whose labels resemble yours. The analogy breaks here. Real photographs have no natural labels, so the system invents the boxes from the data. A good match can sit in a box you never opened.

In one precise sentence: similarity search turns items into vectors, measures distances between them, and uses an index to avoid measuring against all of them.

Step 1: Turn every item into a vector

A model converts each item into a vector, so that items the model finds similar get vectors that lie close together. For text, the sentence-embedding model of Reimers and Gurevych, built on the Bidirectional Encoder Representations from Transformers (BERT) network, produces sentence vectors that "can be compared using cosine-similarity" (Reimers and Gurevych, 2019). The same idea works for images, audio and table rows, because the search only ever sees the vectors. Input: an item. Output: a list of, say, 64 or 384 numbers.

This is done once per stored item, before any query arrives, and once per query when it arrives. What you now know: after this step the search problem has no text or pixels left in it, only points.

Step 2: Pick one distance and use it everywhere

A distance turns two vectors into one number that says how far apart they are. Euclidean distance (L2) measures the straight line between the points. The dot product multiplies matching entries and adds them. Cosine similarity compares only the angle between the vectors. Take a = (3, 4), b = (6, 8) and c = (4, 3), all illustrative.

Cosine similarity of a with b is 1.0, because they point the same way, while their Euclidean distance is 5.0. Cosine of a with c is 0.96 and their Euclidean distance is 1.41.¹ Two metrics disagree about which is closer, so the choice matters. If you scale every vector to length one, all three metrics give the same ranking, which is how Faiss supports cosine: "normalize vectors beforehand" and use an inner-product index.

Step 3: Compare the query with every vector (exact search)

Exact search, also called brute force, computes the distance from the query to every stored vector and returns the k smallest. Its answer is perfect by definition, and by default pgvector works this way: "By default, pgvector performs exact nearest neighbor search, which provides perfect recall." The cost is linear. For 20,000 vectors of 64 numbers, one query needs 20,000 distance computations, which is 1,280,000 multiply-adds, over 5.12 megabytes of vectors in 32-bit floating point.¹ That is nothing today. At a hundred million vectors the same scan is five thousand times larger per query, and it repeats for every user. Input: one query and all vectors. Output: the exact top k, at a cost that grows with the collection.

Step 4: Group the vectors so a query can skip most of them

An inverted-file index (IVF) first splits the vectors into groups by clustering them, then stores each vector under its nearest group centre. At query time it finds the few centres closest to the query and scans only those groups. pgvector describes it this way: an IVFFlat index "divides vectors into lists, and then searches a subset of those lists." The number of lists searched is a dial, called nprobe in Faiss.

In our test of 100 lists, probing 1 list scanned 271 of 20,000 vectors (1.4%) and found 74.9% of the true neighbours. Probing 2 lists found 94.6% at 2.3% of the vectors, and probing 5 lists found 99.6% at 5.5%.¹ That dial is the answer to the hook: the speed you gain is bought with recall, and you set the price per query.

Step 5: Or walk a graph instead, then measure recall

A graph index links each vector to near neighbours and finds the answer by hopping from link to link toward the query. The Hierarchical Navigable Small World (HNSW) index stacks several such graphs, with sparse ones above dense ones, so the search starts with long hops and ends with short ones. Its authors report that this scale separation "allows a logarithmic complexity scaling" (Malkov and Yashunin, 2016). Its dial is the size of the candidate list kept during the walk, called efSearch.

In our test, efSearch of 10 gave recall 0.841, 16 gave 0.918 and 64 gave 0.999.¹ Keep efSearch at least as large as k: pgvector's README notes that "Results are limited by the size of the dynamic candidate list", so a list of 4 could never return ten rows. Whatever index you pick, the last step is the same: compare its results with exact search on a sample of queries and report recall.

1 · Embed2 · Distance3 · Exact scan4 · Lists5 · GraphReplay

Step-by-step description

1. Every item becomes a vector.
2. One metric defines close.
3. Compare with all 20,000 vectors.
4. Scan only the nearest lists.
5. Hop toward the query, then check recall.

• Exact search compares the query with every stored vector.
• An inverted-file index scans only the lists nearest the query.
• A graph index finds neighbours by hopping from link to link.

Worked example

We ran Faiss 1.13.2 on 20,000 synthetic vectors of 64 numbers drawn from 50 Gaussian clusters, with 500 queries and k = 10. The data is illustrative and well separated, which is a best case for IVF: the 50 cluster centres are at least 8.44 apart, points sit a mean 2.79 from their own centre, and all of the true top ten neighbours lay in the query's own cluster. Real embeddings overlap more and need more probes, so the results show the shape of the trade-off rather than a benchmark.¹ Exact search is the reference: recall 1.0 at 20,000 distance computations per query. The IVF index used 100 lists. The table lists the dial and its price.

The metrics experiment confirms Step 2. After scaling every vector to length one, cosine similarity, inner product and Euclidean distance returned the same set of ten neighbours for all 500 queries.¹ At real scale this trade-off sets the hardware bill: building a k-nearest-neighbour graph over 1 billion vectors, which is one search per vector, took the Faiss authors under 12 hours on four graphics processing units (GPUs) (Johnson, Douze and Jegou, 2017).

Text description of the diagram

• Probing 1 list gave a recall of 0.749 at 1.4% of the vectors.
• Probing 5 lists gave a recall of 0.996 at 5.5% of the vectors.

Trade-offs and edge cases

Every index trades four things: query speed, recall, memory and build time. The pgvector documentation states the trade between its two index types: HNSW "has better query performance than IVFFlat (in terms of speed-recall tradeoff), but has slower build times," and IVFFlat builds faster and uses less memory. Its defaults, as of October 2026, are 16 connections per layer and a search list of 40 for HNSW; raising the search list "provides better recall at the cost of speed." Exact search stays the right choice when the collection is small enough to scan within your latency budget, because it has no tuning and no recall loss.

Two edge cases catch candidates. First, the index inherits the embedding model's flaws: similarity search finds what the vectors call close, so a poor embedding gives confident wrong answers at any recall. Second, the best candidate under the vector distance is not always the best answer, which is why many systems retrieve a shortlist and reorder it with a cross-encoder reranker. The transformer-based models that produce the vectors are covered in the transformers hub.

Text description of the diagram

• Stored images are embedded once and their vectors go into the index.
• The query image is embedded by the same model.

How to answer it in an interview

Say it in this order: why exact fails, which index and why, what it costs, how you measure.

Common mistakes

• "Similarity search is just cosine similarity" (wrong). Cosine is one distance. The hard part is finding neighbours without scanning everything. (Right: "the distance defines closeness; the index decides how much of the data I examine.")
• "An approximate index returns the right answer" (wrong). It returns most of the right answers. (Right: "I'd report recall at 10 against exact search.")
• "Higher recall is free" (wrong). On our test, recall rose from 0.749 to 0.996 while the share scanned rose from 1.4% to 5.5%. (Right: "recall costs scanned vectors, so I'd set it from the latency budget.")
• "Any embeddings will do for any metric" (wrong). A distance should match how the model was trained. (Right: "I'd normalise or follow the model card's recommended metric.")

Follow-up questions

What is the difference between hybrid search and similarity search?

Similarity search compares vectors that capture meaning, so a query can match a document that shares no words with it. Keyword search matches the words themselves. Hybrid search runs both and merges the two ranked lists, which helps when exact terms such as product codes matter; see hybrid search.

How does a vector database use cosine similarity?

A vector database stores the vectors and applies a distance, often cosine similarity, inside its index. Cosine equals the dot product only when vectors have length one: for the illustrative vectors in Step 2, a and b have cosine 1.0 but dot product 50. After normalising, cosine, dot product and Euclidean distance gave identical top ten sets for all 500 test queries.

What is Faiss and how does it relate to a vector database?

Faiss is Meta's open-source library for similarity search over dense vectors, with exact, IVF and HNSW indexes; we used it for every number on this page (Faiss indexes wiki). It is a library you call, whereas a vector database adds storage, filtering and a server around an index such as these. To choose the probe dial, start from a recall target and a latency budget, then plot recall against vectors scanned for 100 or more real queries: on our test 5 of 100 lists reached 0.996.

When is exact search the right choice?

When the collection is small enough that a full scan fits the latency budget, or when a missed neighbour is unacceptable. pgvector makes exact search its default for this reason.

What does an image similarity search architecture look like?

An embedding model encodes every image once and the vectors go into an index. At query time the same model encodes the query image, the index returns the nearest vectors, and a final stage can reorder them. See the diagram under trade-offs, and the AI engineer question list for neighbouring topics.

Sources

1. Billion-scale similarity search with GPUs — arXiv (Johnson, Douze and Jegou), 28 Feb 2017
2. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — arXiv (Malkov and Yashunin), v4 revised 2018-08-14, 30 Mar 2016
3. Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks — arXiv (Reimers and Gurevych), 27 Aug 2019
4. pgvector: open-source vector similarity search for Postgres — pgvector project README (read 2026-10-24), 24 Oct 2026
5. Faiss indexes — Faiss wiki, Meta (read 2026-10-24), 24 Oct 2026