ANN Indexes Guide

TL;DR

• ANN (Approximate Nearest Neighbor) indexes find close vectors without comparing the query to every point - essential beyond ~100K embeddings.

• HNSW is the default in many vector databases: a multi-layer proximity graph with excellent latency/recall and higher RAM use.

• IVF / IVF-PQ partition space into clusters (and often compress residuals) - strong for very large corpora and memory-constrained deployments.

• DiskANN and ScaNN target billion-scale or cost-sensitive settings with disk-aware graphs or learned anisotropic quantization.

• Flat (exact) indexes remain the evaluation baseline and a valid production choice for small or heavily pre-filtered sets.

Why This Matters

Every RAG and semantic search system eventually reduces to: given query vector (q), return the (k) closest document vectors. Brute force is correct and simple until corpus size makes it too slow or too expensive. The index type you choose determines whether that query takes 3 ms or 300 ms, whether the machine needs 64 GB or 512 GB of RAM, and whether recall@10 is 0.99 or 0.85.

Teams often pick whatever their vector database defaults to - frequently HNSW - then discover build times, memory, or filtered-search behavior do not match their workload. Understanding ANN structures lets you tune the right knobs (efSearch, nprobe, M) and know when to switch families instead of blindly scaling hardware.

The Problem ANN Indexes Solve

Exact search is linear in corpus size. For (n) vectors of dimension (d), exact k-NN is (O(nd)) per query. At (n=10^7), (d=1536), a single query is billions of floating-point operations if done naively on CPU.

High dimensions break naive spatial indexes. KD-trees and ball trees degrade toward linear scan as dimensionality grows - the classic curse of dimensionality. Embedding search needs structures designed for approximate high-dimensional similarity.

Production needs sub-linear query time with bounded error. You rarely need perfect nearest neighbors for RAG. You need the right chunk in the top-10 often enough that generation succeeds. ANN formalizes that tradeoff.

ANN indexes solve scale: millisecond similarity search over millions to billions of embeddings with tunable recall.

What Is an ANN Index?

An Approximate Nearest Neighbor index is a data structure built over a set of vectors that supports queries of the form:

Return (k) points believed to be nearest to (q) under metric (\delta) (cosine, L2, inner product), possibly missing some true neighbors.

Properties that matter in production:

A flat index stores vectors with no approximation structure - exact search. Everything else is ANN.

How ANN Indexes Work

Flat (Exact) Index

Store vectors in a contiguous matrix. At query time, compute distance to all (or to a filtered subset) and take top-(k).

• Pros: Perfect recall, trivial updates, best baseline for evaluation.
• Cons: Does not scale for unfiltered search over large (n).
• Use when: (n) is small, GPU exact search is available, or metadata filters reduce candidates to tens of thousands.

HNSW (Hierarchical Navigable Small World)

HNSW builds a layered graph. Upper layers are sparse (long-range links). Layer 0 contains all points with dense local links.

Search:

1. Enter at the top layer.
2. Greedy-walk to the nearest neighbor of (q) at that layer.
3. Descend one layer; repeat.
4. At layer 0, expand a dynamic candidate list of size efSearch and return best (k).

Insert uses a similar search to find neighbors and link the new node (controlled by M, efConstruction).

flowchart TB
    Q["Query vector q"] --> L2["Layer 2: long-range greedy walk"]
    L2 --> L1["Layer 1: refine neighborhood"]
    L1 --> L0["Layer 0: expand efSearch candidates"]
    L0 --> TopK["Return top-k neighbors"]

Key parameters:

HNSW dominates general-purpose low-latency retrieval in Qdrant, Weaviate, pgvector HNSW, and many managed services.

IVF (Inverted File Index)

IVF trains a coarse quantizer (k-means) with nlist centroids. Each vector is assigned to its closest centroid; posting lists store residual vectors (or IDs).

Search: find the nprobe closest centroids to (q), scan only those lists, return top-(k).

• Larger nlist → finer cells, shorter lists, more sensitive training.
• Larger nprobe → higher recall, higher latency.

IVF alone still stores full-precision (or lightly quantized) vectors in the inverted lists.

IVF-PQ

Combine IVF with product quantization:

1. Assign vector to a coarse cell (IVF).
2. Encode the residual (or vector) with PQ codes.
3. At query time, probe nprobe cells and compute ADC distances over codes.
4. Optionally rescore top candidates with full vectors.

This is the classic Faiss path for 100M–1B+ vectors when RAM is limited. Milvus exposes IVF_PQ and related types extensively.

DiskANN

DiskANN (Microsoft) keeps a graph-based index where the full neighborhood structure can live on SSD, with compressed vectors (often PQ) in memory to guide navigation. It targets high recall at billion scale without requiring the entire float graph to be RAM-resident.

Use when:

• Corpus is huge.
• RAM per node is the constraint.
• You can accept slightly higher latency than in-memory HNSW for large cost savings.

ScaNN

ScaNN (Google) combines partitioning with anisotropic vector quantization - it allocates quantization error with ranking loss in mind (not only reconstruction). Strong for large-scale inner-product / cosine retrieval, especially in Google's published benchmarks and open-source library usage.

Think of ScaNN as a competitive alternative in the IVF + learned quantization design space rather than a drop-in HNSW replacement inside every vector DB.

Other Structures You Will See

Engineering Insight

💡 Key Idea - Graph indexes (HNSW, DiskANN) navigate neighborhoods; inverted-file indexes (IVF, IVF-PQ, ScaNN-style) prune partitions. Same goal, different memory and update tradeoffs.

Architecture

ANN sits between embedding and application logic:

flowchart LR
    Docs["Documents"] --> Emb["Embed"]
    Emb --> Build["Build ANN index"]
    Build --> Shard["Shard 0..N"]
    Qry["User query"] --> QEmb["Embed query"]
    QEmb --> Router["Query router"]
    Router --> Shard
    Shard --> Merge["Merge + filter"]
    Merge --> Out["Top-k IDs + scores"]

Managed Pinecone hides index internals; self-hosted Milvus/Qdrant expose them. For engine selection, see best vector databases, Qdrant vs Pinecone, and Milvus vs Qdrant.

Step-by-Step Flow

1. Fix the metric to match the embedding model (cosine, dot product, L2). Wrong metric invalidates any index tuning.

2. Build an exact baseline on a sample (or full set if small). Store true top-(k) neighbors for a query set.

3. Choose an index family from scale and ops constraints (table below).

4. Build with conservative quality settings (higher efConstruction / adequate nlist training sample).

5. Tune query-time knobs (efSearch, nprobe) against recall@k and p95 latency.

6. Add filters and remeasure - filtered ANN often needs higher ef/nprobe or specialized filter strategies.

7. Load-test at target QPS with realistic payload sizes and concurrency.

8. Document rebuild playbooks - embedding model upgrades require full reindex.

Real Production Example

A documentation RAG service indexes 8M chunks (768-d). Target: recall@10 ≥ 0.97 vs exact, p95 latency ≤ 40 ms at 50 QPS, single replica in 64 GB RAM.

"""
Illustrative HNSW search loop (educational).
Production: use Faiss, hnswlib, or your vector DB client.
"""
from __future__ import annotations

import heapq
from dataclasses import dataclass, field

import numpy as np


@dataclass
class HNSWNode:
    id: int
    vector: np.ndarray
    neighbors: dict[int, list[int]] = field(default_factory=dict)  # layer -> ids


class TinyHNSW:
    """Minimal greedy search to show layer descent + ef candidate expansion."""

    def __init__(self, nodes: dict[int, HNSWNode], entry_id: int, entry_level: int):
        self.nodes = nodes
        self.entry_id = entry_id
        self.entry_level = entry_level

    @staticmethod
    def l2(a: np.ndarray, b: np.ndarray) -> float:
        return float(np.sum((a - b) ** 2))

    def search_layer(
        self,
        query: np.ndarray,
        entry_points: list[int],
        ef: int,
        layer: int,
    ) -> list[tuple[float, int]]:
        visited = set(entry_points)
        candidates: list[tuple[float, int]] = []
        results: list[tuple[float, int]] = []

        for ep in entry_points:
            dist = self.l2(query, self.nodes[ep].vector)
            heapq.heappush(candidates, (dist, ep))
            heapq.heappush(results, (-dist, ep))  # max-heap via negation

        while candidates:
            dist, cid = heapq.heappop(candidates)
            worst = -results[0][0]
            if dist > worst and len(results) >= ef:
                break
            for nid in self.nodes[cid].neighbors.get(layer, []):
                if nid in visited:
                    continue
                visited.add(nid)
                d = self.l2(query, self.nodes[nid].vector)
                if len(results) < ef or d < -results[0][0]:
                    heapq.heappush(candidates, (d, nid))
                    heapq.heappush(results, (-d, nid))
                    if len(results) > ef:
                        heapq.heappop(results)
        return sorted([(-d, i) for d, i in results])

    def query(self, q: np.ndarray, k: int = 10, ef_search: int = 64) -> list[int]:
        ep = [self.entry_id]
        for layer in range(self.entry_level, 0, -1):
            nearest = self.search_layer(q, ep, ef=1, layer=layer)
            ep = [nearest[0][1]]
        top = self.search_layer(q, ep, ef=max(ef_search, k), layer=0)
        return [i for _, i in top[:k]]


def recall_at_k(approx: list[int], exact: list[int], k: int) -> float:
    return len(set(approx[:k]) & set(exact[:k])) / float(k)


# Eval pattern used in production tuning loops
def tune_ef_search(
    index: TinyHNSW,
    queries: np.ndarray,
    exact_neighbors: list[list[int]],
    target_recall: float = 0.97,
) -> int:
    for ef in (32, 64, 128, 256):
        scores = []
        for q, truth in zip(queries, exact_neighbors):
            approx = index.query(q, k=10, ef_search=ef)
            scores.append(recall_at_k(approx, truth, k=10))
        mean_recall = float(np.mean(scores))
        print(f"efSearch={ef} recall@10={mean_recall:.3f}")
        if mean_recall >= target_recall:
            return ef
    raise RuntimeError("Could not meet recall target; increase M/efConstruction or change index")

For IVF-PQ at larger scale, the same evaluation loop applies - sweep nprobe instead of efSearch, and include a rescoring stage when using PQ codes.

Design Decisions

⚠ Common Mistakes

1. Tuning efSearch/nprobe without a recall baseline. Latency numbers without recall@k are meaningless.

2. Using too few IVF training vectors. Under-trained coarse quantizers create unbalanced lists and poor recall.

3. Setting nlist absurdly high for small corpora. Rule of thumb often cited: on the order of (\sqrt{n}) as a starting point - validate, do not cargo-cult.

4. Ignoring filter interaction. Post-filtering HNSW results can return fewer than (k) hits; raise ef or use DB-native filtered search.

5. Comparing indexes across different metrics or embeddings. Benchmarks must hold the embedding model fixed.

6. Forgetting rebuild cost. HNSW rebuilds on 100M vectors are long-running jobs - plan capacity.

7. Assuming managed defaults are optimal. Pinecone/Weaviate/Qdrant defaults favor general cases, not your SLO.

Where It Breaks Down

Extremely selective filters. If 0.01% of vectors match a tenant/date predicate, global ANN graphs waste work. Prefer prefiltering, segmented indexes, or payload-aware traversal.

Rapid deletes/updates. Graph indexes can accumulate tombstones or fragmentation; IVF lists become stale. Schedule compaction.

Metric mismatch. Training IVF on L2 space while querying with unnormalized cosine semantics produces mysterious recall loss.

Multi-vector / late interaction. ColBERT-style indexes need multi-vector-aware retrieval (see late-interaction retrieval); single-vector HNSW per doc is a different design.

Ultra-low latency + ultra-high recall on huge (n). You may need more replicas, better hardware, or accepting slightly lower recall - physics still applies.

Running in Production

Best Practice

✅ Best Practices - Keep an exact-neighbor eval set, tune query-time parameters continuously as the corpus grows, alert on recall regressions after reindexes, and capacity-plan for graph RAM not just raw vector bytes.

Important

After every embedding model change, rebuild indexes and re-run recall evaluation. Old graph edges over new vectors are not a thing - you must re-embed and reindex.

Ecosystem

• Milvus: Broad index catalog (HNSW, IVF_FLAT, IVF_PQ, Disk-oriented options depending on version/config).

• Qdrant: HNSW-first with quantization and rich filtering.

• Weaviate: HNSW with hybrid search and compression features.

• Pinecone: Managed ANN; less knobs, strong ops defaults.

• pgvector: IVFFlat and HNSW inside PostgreSQL for simpler stacks.

Survey options on best vector databases. Deep comparisons: Qdrant vs Pinecone, Milvus vs Qdrant.

Open-source libraries underneath many stacks: Faiss, hnswlib, ScaNN, DiskANN.

Related Technologies

• Vector Quantization: PQ/SQ/binary codes that IVF-PQ and disk-based indexes rely on.

• Vector Search: The retrieval problem ANN indexes implement.

• Embeddings: Vector source and metric constraints.

• Vector Databases: Operational systems wrapping ANN.

• Metadata Filtering: Predicates that change ANN behavior.

• RAG: Primary application of ANN-backed retrieval.

Learning Path

Prerequisites: Embeddings · Vector Search

Next topics: Vector Quantization · Metadata Filtering · Hybrid Search

Estimated time: 55 min · Difficulty: Intermediate

FAQs

What recall should I target?

For RAG, many teams aim for recall@10 ≥ 0.95–0.99 against exact search on a golden set. Higher-stakes domains push higher; noisy corpora can tolerate slightly less if a reranker follows.

Is HNSW always better than IVF?

No. HNSW usually wins on latency/recall for in-memory mid-scale workloads. IVF-PQ often wins on memory and billion-scale economics. Benchmark on your vectors.

How do I choose M for HNSW?

Start with library defaults (often 16–32). Increase if recall plateaus below target even at high efSearch. Watch RAM: each bump in M multiplies edge storage.

What is a good nprobe?

Start with a small fraction of nlist (e.g. 1–5%) and increase until recall meets SLO. There is no universal constant.

When is a flat index acceptable in production?

Small corpora, strong prefilters that shrink candidates, offline batch jobs, or evaluation oracles. Also GPU exact search for medium (n).

Does ANN work with cosine similarity?

Yes - either normalize vectors and use inner product/L2 on the unit sphere, or use an engine that implements cosine natively. Be consistent between build and query.

How does metadata filtering affect HNSW?

Naïve post-filtering can underfill k. Engines implement filtered traversal or iterative ef expansion. Always measure filtered recall separately.

Can I update HNSW online?

Most systems support upserts/deletes. Heavy churn may require compaction. IVF often prefers periodic rebuilds for best quality.

What is the difference between IVF_FLAT and IVF_PQ?

IVF_FLAT stores full vectors in lists (better recall, more memory). IVF_PQ stores PQ codes (less memory, needs careful tuning/rescoring).

Is DiskANN only for Microsoft stacks?

The research and open-source implementations influenced disk-aware designs broadly. Check whether your specific vector DB offers a DiskANN-like index or similar SSD-primary mode.

How do shards merge ANN results?

Each shard returns local top-(k) (or top-(k')). The coordinator merges by score. Global recall can drop if (k') is too small - over-fetch per shard.

Should I index with float16?

Often yes as a first memory cut before PQ. Validate recall; combine with ANN parameters as usual.

How often should I rebuild?

After embedding model changes (mandatory), after major corpus replacements, and when delete/update churn degrades latency or recall. Otherwise prefer incremental upserts.

Where do ScaNN and Faiss fit if I use a vector DB?

Many databases embed Faiss-like IVF-PQ internally. ScaNN is often used directly in custom retrieval stacks. Managed DBs may not expose ScaNN by name.

References

• Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using HNSW
• Faiss indexes documentation
• DiskANN paper / Microsoft DiskANN
• ScaNN: Efficient Vector Similarity Search (Google)
• Milvus index docs
• Qdrant indexing docs

Further Reading

• Vector Quantization guide
• Vector Search guide
• Best vector databases ranking
• Qdrant vs Pinecone
• Milvus vs Qdrant
• hnswlib repository

Summary

• ANN indexes make high-dimensional similarity search sub-linear with tunable recall.
• HNSW is the common low-latency default; IVF/IVF-PQ and DiskANN/ScaNN address scale and memory.
• Flat exact search remains the evaluation baseline and a valid small-scale production choice.
• Tune efSearch / nprobe against measured recall@k, not folklore.
• Filters, updates, and sharding change the winning index - remeasure under realistic predicates.
• Rebuild after embedding changes; treat index type as a capacity decision, not a one-time checkbox.