Vector Indexes and Approximate Search

Exact search does not scale

Comparing the query with every vector (brute force) is exact but slow for millions of vectors. Approximate nearest neighbour (ANN) indexes such as HNSW (a layered graph), IVF (clusters) and quantised variants find near-best matches much faster, trading a little recall for speed and memory. For a few thousand chunks, brute force is fine and simplest. Larger systems use a vector database or a search engine with vector support (for example pgvector, Elasticsearch/OpenSearch, Qdrant, Milvus, Pinecone, FAISS). Tune the recall-versus-latency settings against your own evaluation set.

Size and cost arithmetic, run

I ran this plain-Python (standard library only) example. One million 768-dimension float32 vectors take about 3.07 GB; 100 brute-force queries need 76.8 billion multiplications; 8-bit quantisation cuts the vector storage to a quarter.

import math

# brute-force nearest neighbour cost: queries * documents * dimensions multiplications
docs, dim, queries = 1_000_000, 768, 100
ops = docs * dim * queries
print("multiplications per 100 queries:", f"{ops:,}")
print("float32 index size (GB):", round(docs * dim * 4 / 1e9, 2))
print("with 8-bit quantisation (GB):", round(docs * dim * 1 / 1e9, 2))

Output:

multiplications per 100 queries: 76,800,000,000
float32 index size (GB): 3.07
with 8-bit quantisation (GB): 0.77

Brute force is fine for small sets

Below roughly 100,000 vectors a plain exact search is often fast enough and removes ANN tuning entirely.

Quick check: What do ANN indexes trade for speed?

• All accuracy
• A little recall (they may miss a true nearest neighbour)
• The ability to store metadata
• The language support