Vector stores & ANN indexes

The retrieval operation

Given a query vector q of dimension d and n stored chunk vectors, retrieval finds the k vectors most similar to q. With cosine similarity, this means computing cos(q, v_i) for every stored vector and returning the top k.

The naive approach — compute similarity against every vector — is exact but O(n * d) per query. At 1 million chunks with 1,536 dimensions, that is roughly 6 billion floating-point operations per query. It works for small indices. It does not work at scale.

Approximate nearest-neighbor (ANN) indexes trade a small recall loss for orders-of-magnitude speedup.

Brute force (exact search)

For corpora under ~100K vectors, exact search is viable and produces perfect recall — you always find the true top-k.

import numpy as np

def exact_search(
    query_vec: np.ndarray,
    corpus_vecs: np.ndarray,
    k: int = 5,
):
    similarities = corpus_vecs @ query_vec  # assumes normalized
    top_k_idx = np.argpartition(similarities, -k)[-k:]
    top_k_idx = top_k_idx[np.argsort(similarities[top_k_idx])[::-1]]
    return top_k_idx, similarities[top_k_idx]

np.argpartition is O(n) for the partitioning step, making this faster than a full sort when k is much smaller than n. Use exact search as your baseline when benchmarking ANN recall.

HNSW (Hierarchical Navigable Small World)

HNSW is the dominant ANN algorithm in production vector stores. It builds a multi-layer graph where each node is a vector and edges connect nearby vectors. Top layers are sparse (long-range jumps); the bottom layer is dense (local neighborhood). A query traverses from top to bottom, greedily following edges toward the nearest neighbor at each layer.

Parameters

• `m` — edges per node. Higher = better recall, more memory. Typical range: 16–64.
• `ef_construction` — search width during index building. Higher = better graph quality, slower build. Typical: 64–200.
• `ef_search` — search width at query time. Higher = better recall, higher latency. Typical: 40–200. This is the primary runtime knob.

Performance

• Build time: O(n * log n)
• Query time: O(log n)
• Memory: full graph in RAM — vectors plus edge lists. The graph adds roughly 50–100% overhead on top of raw vector storage.
• Recall: 95–99% at reasonable ef_search settings.

For 1M vectors at 1,536 dimensions, raw vectors consume ~6 GB. The HNSW index brings total memory to 9–12 GB.

IVF (Inverted File Index)

IVF partitions the vector space into nlist clusters using k-means, then assigns each vector to its nearest cluster centroid. At query time, only the nprobe closest clusters are searched, reducing the search space by a factor of nlist / nprobe.

Parameters

• `nlist` — number of clusters. Typical: sqrt(n) to 4 * sqrt(n).
• `nprobe` — clusters searched per query. Higher = better recall, higher latency. Typical: 1–20% of nlist.

IVF uses less memory than HNSW (no graph overhead) and supports disk-backed storage. Its recall/speed tradeoff is generally worse than HNSW at moderate scale, but it handles billions of vectors where HNSW's memory cost is prohibitive.

pgvector: vector search in Postgres

pgvector adds vector operations to PostgreSQL — the same database many applications already run. For RAG systems on a Postgres-backed stack (Supabase, for instance), this avoids deploying and synchronizing a separate vector service.

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE chunks (
    id        BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    content   TEXT NOT NULL,
    source    TEXT NOT NULL,
    page      INT,
    embedding vector(1536)
);

CREATE INDEX chunks_embedding_idx ON chunks
    USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 128);

Query with a similarity search and metadata filter:

SELECT id, content, source, page,
       1 - (embedding <=> $1::vector) AS similarity
FROM chunks
WHERE source = 'api-reference.md'
ORDER BY embedding <=> $1::vector
LIMIT 5;

The <=> operator computes cosine distance (1 - cosine_similarity). The HNSW index accelerates this from a full table scan to an approximate graph traversal. The WHERE clause pre-filters — only matching rows enter the search.

ef_search can be set per-session:

SET hnsw.ef_search = 100;

pgvector vs. dedicated vector stores

Dedicated stores (Pinecone, Weaviate, Qdrant) offer features pgvector lacks: built-in hybrid search, automatic sharding, managed infrastructure, richer filtering operators. pgvector's advantage is colocation — vectors, metadata, and application data live in one database, eliminating synchronization between two systems.

For up to ~5M vectors, pgvector with HNSW handles production workloads. Beyond that, or when you need built-in hybrid search, dedicated stores earn their operational overhead.

Index tuning in practice

Start with HNSW defaults (m=16, ef_construction=128). Measure recall against a brute-force baseline on a test set of labeled queries:

• If recall is below target (typically 95%+), increase ef_search.
• If queries are too slow, decrease ef_search or reduce vector dimensions (Matryoshka models make this easy).
• If the index doesn't fit in memory, consider IVF with product quantization or a disk-backed store.

The important thing to internalize: ANN tuning is always a recall vs. latency tradeoff. You are deciding how much search accuracy to sacrifice for speed. Measure both — and use exact search as the ground truth.

Key takeaways

• Exact search is O(n * d) per query — viable for small corpora, not at scale. ANN indexes trade a small recall loss for orders-of-magnitude speedup.
• HNSW dominates in practice: O(log n) queries, 95–99% recall, at the cost of in-memory graph storage. Tune ef_search for your recall/latency target.
• pgvector puts vector search inside Postgres — one database for vectors, metadata, and application data. Use HNSW indexing and SQL WHERE clauses for filtered search.
• For up to ~5M chunks, pgvector with HNSW is sufficient. Dedicated stores add value at larger scale or when you need built-in hybrid search.