Ann Algorithms

ANN Algorithms

Exhaustive vs Approximate

Exhaustive (brute-force) search compares the query against every stored vector — 100% recall, O(N) per query. Approximate Nearest Neighbor (ANN) trades a few percent recall for 10-1000x speedup.

Break-even heuristic:

• Under ~100k vectors: brute-force is fine (use flat in FAISS / flat in ES).
• 100k-10M: HNSW is the go-to.
• 10M-1B+: HNSW with quantization, IVF+PQ, DiskANN, or a sharded combo.

HNSW (Hierarchical Navigable Small World)

Multi-layer graph where upper layers are sparse long-range links and lower layers are dense local links. Search starts at the top, greedy-descends to the bottom.

Parameters

Memory footprint per vector: 4*d + 8*M + 4*M bytes (vector + neighbor IDs + neighbor distances per layer).

When HNSW is the right call

• Dataset fits in RAM.
• Mixed read/write workload.
• Recall target >95%.
• Latency target <50ms at moderate QPS.

When HNSW hurts

• Insert-heavy workloads where graph churn degrades quality.
• Vectors >> RAM: graph edges are random-access heavy, slow on SSD.

FAISS HNSW

import faiss, numpy as np

d = 1024
index = faiss.IndexHNSWFlat(d, 32)          # M=32
index.hnsw.efConstruction = 200
index.add(corpus)                            # corpus: (N, d) float32

index.hnsw.efSearch = 100
D, I = index.search(queries, k=10)

IVF (Inverted File / Cell Probes)

Cluster vectors into nlist Voronoi cells. At query time, search only the nprobe nearest cells.

quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist=4096, faiss.METRIC_L2)
index.train(sample)     # needs a representative training set (~256*nlist points)
index.add(corpus)
index.nprobe = 32
D, I = index.search(queries, 10)

IVF alone (IVFFlat) is memory-efficient (no graph) but less accurate than HNSW at equal memory. Its real strength is combining with PQ.

IVF + PQ (IVFPQ)

Product Quantization splits each vector into m subvectors and quantizes each to one of ksub centroids. Combines with IVF for massive compression.

m = 64       # subvector count (must divide d)
nbits = 8    # bits per code per subvector -> 256 centroids
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer, d, nlist=8192, m, nbits)
index.train(sample)
index.add(corpus)
index.nprobe = 64

Memory: m bytes per vector (e.g. 64 bytes vs 4096 bytes for d=1024). Enables 100M+ vector indexes on a single machine. Pair with reranking on full vectors for top-K.

ScaNN (Google)

Uses anisotropic vector quantization tuned for maximum inner product search. Typically 2-4x faster than HNSW at equal recall on dense embeddings, especially with quantization.

import scann
import numpy as np

searcher = (
    scann.scann_ops_pybind.builder(corpus, 10, "dot_product")
    .tree(num_leaves=2000, num_leaves_to_search=100, training_sample_size=250_000)
    .score_ah(dimensions_per_block=2, anisotropic_quantization_threshold=0.2)
    .reorder(100)
    .build()
)
neighbors, distances = searcher.search_batched(queries)

Best for: read-heavy, inference-server-style workloads with rebuild windows. Updates require a retrain.

DiskANN (Microsoft)

Graph-based index designed for SSDs. Stores the graph + full vectors on disk, loads only what a query needs.

Strengths:

• Handles billions of vectors on a single SSD-equipped box.
• Good recall with low per-query memory.

Costs:

• Higher p99 latency (SSD I/O).
• Complex build / ingest pipelines.

Used under the hood by Vespa, Milvus (disk variant), and some managed offerings.

LSH (Locality Sensitive Hashing)

Hash-based; projects vectors into buckets via random hyperplanes. Fast insert, fast query, but recall is mediocre on modern embeddings.

index = faiss.IndexLSH(d, nbits=1024)   # nbits = number of hash bits
index.add(corpus)
D, I = index.search(queries, 10)

Modern use cases: dedup / near-duplicate detection on huge, low-dim, sparse-ish data, or as a prefilter before reranking. NOT the first choice for neural embeddings.

Decision Matrix

Recall / Latency / Memory Tradeoff

Memory   Latency  Recall
-----    -------  ------
Flat     worst    best recall, slowest, full vectors only
HNSW     high     low latency, near-perfect recall
IVFFlat  low      moderate latency, good recall
IVFPQ    lowest   fast, lower recall (rescore to recover)
DiskANN  disk     moderate latency, good recall on disk
ScaNN    low      lowest latency, high recall (static data)
LSH      low      fastest, poor recall on dense

Rule: tune for a target recall (say 95% or 98%), then compare QPS and RAM per provider.

Benchmarking

import numpy as np, time

def recall_at_k(gt: np.ndarray, pred: np.ndarray, k: int) -> float:
    # gt, pred: (Q, k) arrays of doc IDs
    return np.mean([
        len(set(pred[i, :k]) & set(gt[i, :k])) / k
        for i in range(len(gt))
    ])

# Compute ground truth with brute force on a sample
flat = faiss.IndexFlatL2(d)
flat.add(corpus)
_, gt = flat.search(queries, 10)

for ef in [32, 64, 128, 256, 512]:
    index.hnsw.efSearch = ef
    t = time.perf_counter()
    _, pred = index.search(queries, 10)
    ms = (time.perf_counter() - t) / len(queries) * 1000
    print(f"ef={ef:3d}  recall@10={recall_at_k(gt, pred, 10):.3f}  {ms:.2f} ms/q")

Anti-Patterns

Production Checklist

• Index type chosen by dataset size + latency budget + RAM
• Recall@k benchmarked on a held-out query set vs brute-force ground truth
• Parameters (m, ef, nlist, nprobe) documented in config
• Training set size for IVF/PQ verified (at least 256 * nlist)
• Update strategy defined (append, rebuild cadence)
• Memory / disk footprint budgeted
• Rescoring with full-precision vectors for quantized indexes
• Fallback brute-force path for tiny tenants or eval