Vector Databases & ANN Indexes

Embeddings turn text into vectors. A vector database makes those vectors usable at product scale: search, filter, update, and retrieve the nearest neighbors fast enough to sit inside a user request.

The hard part is that exact nearest-neighbor search is linear. Comparing one query against ten thousand vectors is fine. Comparing it against a hundred million vectors, at interactive latency, is a different system.

The mental model

Exact k-nearest-neighbor search is conceptually simple: score every vector, sort, return the top k.

import math

def cosine(a, b):
    dot = sum(x * y for x, y in zip(a, b))
    na = math.sqrt(sum(x * x for x in a))
    nb = math.sqrt(sum(y * y for y in b))
    return dot / (na * nb)

def exact_search(query, rows, k):
    scored = [(cosine(query, row["vector"]), row) for row in rows]
    scored.sort(key=lambda item: item[0], reverse=True)
    return scored[:k]

That is O(N · d) work per query for N vectors of dimension d, plus sorting. Approximate nearest neighbor (ANN) indexes avoid scoring everything. They trade a little recall for much lower latency.

Why exact kNN stops scaling

The brute-force scan is attractive because it is correct and operationally simple. For a small corpus, it is often the right answer. It breaks when any of these grow:

• N — more vectors means more dot products per query.
• d — larger embeddings make every comparison more expensive.
• QPS — even a tolerable single-query scan becomes expensive under traffic.
• Filters — tenant, language, ACL, and freshness constraints change which vectors are eligible.

A flat index over 50k vectors may be simpler and more reliable than a tuned ANN index. A flat scan over 500M vectors will dominate your latency budget.

ANN: search less, miss a little

ANN indexes precompute structure so the query visits a promising subset of the space. The result is not guaranteed to be the exact top k; you measure it with recall@k: of the true top k, how many did the approximate search return?

For RAG, perfect recall is not always necessary. If the answer is supported by several similar chunks, returning one good chunk may be enough. For legal or medical retrieval, missing the one decisive passage may be unacceptable.

HNSW: a navigable graph

HNSW (Hierarchical Navigable Small World) builds a graph where each vector connects to nearby vectors. Search starts from an entry point, greedily walks to closer neighbors, and refines at lower layers.

The intuition: instead of scanning a city block by block, you use highways to get near the neighborhood, then local roads to find the address.

Important knobs:

• Graph degree — more edges improve recall but use more memory.
• Build effort — more careful insertion improves graph quality but slows indexing.
• Search effort — visiting more candidates improves recall but raises latency.

HNSW is a common default for low-latency, high-recall search when memory is available.

IVF: cluster first, search nearby cells

IVF (Inverted File Index) clusters the vector space into coarse partitions. Each vector belongs to a cluster. At query time, you find the nearest clusters and scan vectors inside only those clusters.

The intuition: sort books by shelf first, then search the few shelves closest to the topic instead of the whole library.

Important knobs:

• Number of clusters — too few means each cluster is large; too many means the right vectors may be split across many cells.
• Probes — searching more clusters improves recall and latency gets worse.
• Training sample — bad clustering produces bad partitions.

IVF is useful when memory is tighter or when the vector store can pair it with compression.

Metadata filtering

Real retrieval almost never asks for “nearest vectors globally.” It asks for nearest vectors the user is allowed to see, in the right product area, language, time range, or document type.

There are two broad strategies:

• Pre-filter — apply metadata constraints before vector search. Correct and safe, but may leave too few vectors for the ANN index to work well.
• Post-filter — search broadly, then discard ineligible results. Fast and easy, but can return fewer than k results or miss eligible neighbors.

Security filters, especially tenant and ACL filters, should be enforced before the model sees text. Do not rely on the generator to ignore unauthorized chunks.

Pattern recognition

Variations

Worked problems

def choose_index(num_vectors: int, qps: int, strict_latency_ms: int) -> str:
    if num_vectors <= 100_000 and qps <= 10 and strict_latency_ms >= 100:
        return "flat"
    if num_vectors <= 50_000_000:
        return "hnsw"
    return "ivf_or_sharded_hnsw"

def recall_at_k(exact_sets, approx_sets):
    found = 0
    total = 0
    for exact, approx in zip(exact_sets, approx_sets):
        exact = set(exact)
        approx = set(approx)
        found += len(exact & approx)
        total += len(exact)
    return found / total if total else 0.0

print(390 / 500)  # 0.78

def retrieve_for_user(vector_db, embed, question, user, k=5):
    query_vec = embed(question)
    filters = {
        "tenant_id": user.tenant_id,
        "allowed_roles": {"$contains": user.role},
        "status": "published",
    }

    candidates = vector_db.search(
        vector=query_vec,
        top_k=k,
        filter=filters,
        include_metadata=True,
    )

    safe = []
    for item in candidates:
        meta = item["metadata"]
        if meta["tenant_id"] == user.tenant_id and user.role in meta["allowed_roles"]:
            safe.append(item)
    return safe[:k]

The classic pitfall