Vector Search Explained

Vector search, also called vector similarity search, is a retrieval technique that finds the stored vectors closest to a query vector according to a similarity metric. It powers semantic search by comparing embeddings of text, code or images, and returns the k nearest items together with their similarity scores.

• Query vector: The embedding of the search input, produced by the same model that embedded the documents.
• Metric: The similarity or distance function, typically cosine similarity, dot product or Euclidean distance.
• kNN: Exact k-nearest-neighbour search, which compares the query with every stored vector.
• ANN: Approximate nearest neighbour search, which uses an index to examine only a small fraction of the collection.
• Recall: The proportion of true nearest neighbours that an approximate search actually returns.

For example, a codebase search tool embeds the query "retry a failed database call" and returns retry_with_backoff(), db_reconnect_loop() and circuit_breaker() as the three nearest code snippets.

Key Characteristics of Vector Search

• Geometric retrieval: Relevance is defined by proximity in a high-dimensional space rather than by shared terms.
• Metric sensitivity: Cosine similarity ignores vector magnitude, whereas dot product rewards longer vectors.
• Fixed dimensionality: The query and all stored vectors must have identical dimensions from the same embedding model.
• Accuracy and speed trade-off: Exact search guarantees correct neighbours, and approximate search sacrifices a little recall for speed.
• Tunable parameters: Index settings such as graph connectivity in the HNSW algorithm or the number of probed clusters in IVF control recall and latency.
• Modality independence: The same algorithms search text, source code, images and audio once they are embedded.

How Vector Search Works

1. Embedding: Every document, code snippet or passage is converted into a vector and stored with an identifier.
2. Normalisation: Vectors are often scaled to unit length, so cosine similarity reduces to an inexpensive dot product.
3. Indexing: An ANN structure is built, such as a Hierarchical Navigable Small World (HNSW) graph or an inverted file (IVF) index of clusters.
4. Query encoding: The query is embedded with the identical model and normalised in the same way.
5. Candidate search: The index navigates towards the query's neighbourhood, or exact search scores every vector.
6. Top-k selection: The k highest-scoring candidates are returned in descending order of similarity.

Formulation of Distance Metrics

Vector search requires one number that expresses how close two vectors are. Three measures are common, and each compares the query $q$ with a stored vector $x$ coordinate by coordinate:

• $q$: the query vector, and $x$: one stored document or code vector.
• $q_i,x_i$: the individual coordinates of the two vectors in dimension $i$.
• $d$: the number of dimensions, for example 768 for a typical text embedding model.
• $\Vert q\Vert$: the length, or norm, of a vector, calculated from its own dot product.
• $N$: the number of stored vectors in the collection.

In words, Euclidean distance measures the straight-line separation between two points. The dot product increases when two vectors point in a similar direction and also when they are long. Cosine distance considers only the angle between the vectors, so it ignores their magnitude entirely. A smaller distance, or a larger dot product, indicates a closer match.

The cosine distance vs Euclidean distance choice disappears for unit vectors, which have length 1, because the two quantities are then connected by a single identity, where $\theta$ is the angle between the vectors:

A smaller angle therefore always produces a smaller Euclidean distance, so both metrics return an identical ranking, which explains why embeddings are normalised before indexing.

Exact kNN search compares the query with every stored vector, and every comparison processes all $d$ coordinates, so the cost grows with both the collection size and the dimensionality:

The HNSW algorithm avoids most of these comparisons by organising the vectors into a layered proximity graph. The upper layers contain a small sample of vectors connected by long-range links, whereas the bottom layer contains every vector with short-range links. A query enters at the top layer, moves greedily to whichever neighbour is closest, then descends one layer and repeats the procedure. The number of comparisons grows approximately with $\log N$ rather than $N$, at the price of occasionally missing a true nearest neighbour.

The worked example ranks four two-dimensional vectors, with coordinates [retry, database], against the query $q=(2,1)$:

• Euclidean distance: The db-reconnect vector B = (2, 2) lies exactly one unit from the query, so it is the nearest point by straight-line distance.
• Dot product: The retry-guide vector A = (4, 2) is twice as long as the query, so its dot product is the largest.
• Cosine distance: Vector A points in exactly the same direction as the query, so the angle and the cosine distance both equal zero.

• Search cost: For one million stored vectors with 768 dimensions, exact search performs 768 million multiply-add operations for every single query.

import math

# Two-dimensional vectors: [retry, database]
QUERY = [2, 1]  # "retry a failed database call"
DOCS = {
    "A retry-guide":   [4, 2],  # same direction as the query, long document
    "B db-reconnect":  [2, 2],
    "C backoff-util":  [1, 0],
    "D migrations":    [0, 3],
}

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

def euclidean(a, b):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))

def cosine_distance(a, b):
    return 1 - dot(a, b) / (math.sqrt(dot(a, a)) * math.sqrt(dot(b, b)))

print(f"{'document':<15} {'euclidean':>9} {'dot':>5} {'cos dist':>9}")
for name, vec in DOCS.items():
    print(f"{name:<15} {euclidean(QUERY, vec):9.3f} {dot(QUERY, vec):5d} {cosine_distance(QUERY, vec):9.3f}")

# Smaller distance is closer; a larger dot product is closer.
print("euclidean:", [n[0] for n in sorted(DOCS, key=lambda n: euclidean(QUERY, DOCS[n]))])
print("dot:      ", [n[0] for n in sorted(DOCS, key=lambda n: -dot(QUERY, DOCS[n]))])
print("cosine:   ", [n[0] for n in sorted(DOCS, key=lambda n: cosine_distance(QUERY, DOCS[n]))])

# After scaling every vector to length 1, all three metrics agree.
def unit(v):
    return [x / math.sqrt(dot(v, v)) for x in v]
q = unit(QUERY)
print("unit vectors, euclidean:", [n[0] for n in sorted(DOCS, key=lambda n: euclidean(q, unit(DOCS[n])))])

# Cost of exact kNN: one d-dimensional comparison per stored vector.
N, d = 1_000_000, 768
print(f"exact kNN, N = {N:,}, d = {d}: {N * d:,} multiply-adds per query")

document        euclidean   dot  cos dist
A retry-guide       2.236    10     0.000
B db-reconnect      1.000     6     0.051
C backoff-util      1.414     2     0.106
D migrations        2.828     3     0.553
euclidean: ['B', 'C', 'A', 'D']
dot:       ['A', 'B', 'D', 'C']
cosine:    ['A', 'B', 'C', 'D']
unit vectors, euclidean: ['A', 'B', 'C', 'D']
exact kNN, N = 1,000,000, d = 768: 768,000,000 multiply-adds per query

• Three rankings: The same four vectors produce three different orderings, so the similarity metric is a genuine design decision rather than an implementation detail.
• Magnitude effects: The dot product ranks D above C only because D is the longer vector, and it ranks A first for the same reason.
• Normalisation: Once every vector is scaled to length 1, Euclidean distance reproduces the cosine ranking exactly.

In practice, the metric must match the one the embedding model was trained with, and the $O(N\cdot d)$ cost of exact search is the reason large collections rely on an HNSW or IVF index.

Example: Brute-Force Nearest-Neighbour Search in Python

The program below performs exact k-nearest-neighbour search over six code snippet vectors and compares cosine similarity with an unnormalised dot product.

import heapq
import math

# Hand-made vectors for code snippets: [retry, http, database, parsing]
SNIPPETS = {
    "retry_with_backoff()":  [0.9, 0.4, 0.1, 0.0],
    "http_get_json()":       [0.2, 0.9, 0.0, 0.4],
    "db_reconnect_loop()":   [0.7, 0.0, 0.7, 0.0],
    "parse_iso_date()":      [0.0, 0.0, 0.1, 0.9],
    "run_migrations()":      [0.0, 0.0, 2.0, 0.2],  # long file, large norm
    "circuit_breaker()":     [0.8, 0.5, 0.0, 0.0],
}

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

def cosine(a, b):
    return dot(a, b) / (math.sqrt(dot(a, a)) * math.sqrt(dot(b, b)))

def knn(query, k, metric):
    """Exact k-nearest-neighbour search: score every vector, keep the top k."""
    scored = ((metric(query, vec), name) for name, vec in SNIPPETS.items())
    return heapq.nlargest(k, scored)

query = [0.8, 0.3, 0.4, 0.0]  # "retry a failed database call"
for label, metric in [("cosine", cosine), ("dot product", dot)]:
    print(f"Top 3 by {label}:")
    for score, name in knn(query, 3, metric):
        print(f"  {name:<22} {score:.3f}")
print(f"Distance computations per query: {len(SNIPPETS)}, each over {len(query)} dimensions")

Top 3 by cosine:
  retry_with_backoff()   0.942
  db_reconnect_loop()    0.899
  circuit_breaker()      0.888
Top 3 by dot product:
  retry_with_backoff()   0.880
  db_reconnect_loop()    0.840
  run_migrations()       0.800
Distance computations per query: 6, each over 4 dimensions

• Metric choice matters: The run_migrations() vector has a large magnitude, so the unnormalised dot product promotes it above the more relevant circuit_breaker().
• Exactness: Brute-force search always returns the true nearest neighbours, which makes it the reference for measuring ANN recall.
• Linear cost: The number of distance computations equals the collection size, which becomes expensive at millions of vectors.

Applications of Vector Search

• Code search: Finding functions with similar behaviour across a large repository.
• Semantic retrieval: Supplying relevant passages to retrieval-augmented generation pipelines.
• Duplicate detection: Identifying near-identical bug reports, alerts or log patterns.
• Recommendation: Suggesting related runbooks, API examples or documentation pages.
• Anomaly detection: Flagging log lines whose vectors lie far from every known cluster.
• AI search engines: Retrieving candidate pages, as described in how AI search engines work.

Advantages

• Meaning-aware matching: Paraphrased queries retrieve relevant items without shared vocabulary.
• Scalability: ANN indexes answer queries over millions of vectors within milliseconds.
• Generality: One algorithm serves text, code, images and any other embedded content.
• Composability: Vector search combines with metadata filters and keyword retrieval in a single pipeline.

Limitations

• Approximation errors: ANN indexes can miss a true nearest neighbour, especially with aggressive settings.
• Exact tokens: Identifiers such as error codes rank poorly, as shown in keyword search vs semantic search.
• Memory consumption: Graph indexes such as HNSW are usually held in memory, which raises infrastructure cost.
• Re-embedding: Changing the embedding model requires regenerating and re-indexing every stored vector.

Storage, filtering and updates are handled by a vector database, and exact-term weaknesses are addressed by hybrid search.