ANN Indexes Guide

TL;DR

• ANN (Approximate Nearest Neighbor) indexes find close vectors without comparing the query to every point — increasingly important as corpora grow into the hundreds of thousands or millions of vectors.

• 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.

Deployed retrieval 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.

How We Got Here

Vector search did not start with HNSW. Decades of information retrieval research produced spatial trees, hash-based LSH, inverted-file clustering, and product quantization before modern vector databases packaged them for embedding workloads.

Diagram: Evolution of ANN indexes

timeline
    title ANN index evolution
    1970s : KD-trees and ball trees
    2007 : LSH for high dimensions
    2011 : Product Quantization (Faiss)
    2016 : HNSW graph indexes
    2020 : DiskANN SSD-scale graphs
    2020 : ScaNN anisotropic quantization
    2022 : Vector DBs ship HNSW defaults

As embedding corpora grew past millions of vectors, large-scale systems moved from exact scan to graph and inverted-file ANN with tunable recall.

The RAG boom made ANN indexes operational infrastructure. Teams that previously ran exact scan on 50K vectors now index 10M+ chunks and must choose index families explicitly. See Vector Search for the retrieval problem and Vector Quantization for compression that IVF-PQ and disk indexes depend on.

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).

Diagram: HNSW layer descent

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"]

HNSW descends from sparse upper layers to dense layer 0, expanding a candidate list controlled by efSearch.

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:

Diagram: Sharded ANN query path

sequenceDiagram
    participant Q as Query API
    participant R as Router
    participant S1 as Shard 1
    participant S2 as Shard 2
    participant M as Merger
    Q->>R: query vector + filters
    par Scatter
        R->>S1: ANN search
        R->>S2: ANN search
    end
    S1-->>M: local top-k
    S2-->>M: local top-k
    M-->>Q: global top-k

Each shard returns local neighbors; the coordinator merges by score and may over-fetch per shard to preserve global recall.

Diagram: Index build and query architecture

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"]

Offline build creates the ANN structure; online queries embed once and scatter-gather across shards.

Diagram: Index lifecycle states

stateDiagram-v2
    [*] --> Training: IVF nlist
    Training --> Building: graph or postings
    Building --> Ready: serve queries
    Ready --> Tuning: efSearch / nprobe
    Tuning --> Ready
    Ready --> Rebuild: model change
    Rebuild --> Building
    Ready --> Compacting: heavy deletes
    Compacting --> Ready

Embedding model upgrades force rebuild; delete churn may require compaction before recall degrades.

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 patterns

Comparisons

HNSW vs IVF-PQ vs Flat

ANN vs brute force vs keyword-only

Decision tree: choosing an index family

Decision tree: ANN index selection

flowchart TD
    A[Corpus size?] -->|Small / moderate| B[Flat or HNSW]
    A -->|Large millions+| C[RAM budget OK?]
    C -->|Yes| D[HNSW default]
    C -->|Tight| E[IVF-PQ + rescore]
    A -->|Over 10M| F[IVF-PQ or DiskANN]
    D --> G{Heavy filters?}
    G -->|Yes| H[Raise efSearch / segment indexes]
    G -->|No| I[Measure recall@k]
    E --> I
    F --> I

Start with HNSW for in-memory mid-scale; escalate to IVF-PQ or disk-aware indexes when RAM or build time binds.

Compare engines in Best Vector Databases: Milvus vs Qdrant · Qdrant vs Pinecone · pgvector vs Pinecone.

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.

When NOT to Use ANN Indexes

Skip ANN (use exact search or simpler storage) when:

1. Corpus is tiny — under ~50K vectors, flat scan or pgvector exact search is simpler and perfectly accurate.
2. You need guaranteed nearest neighbors — legal or safety-critical matching may require exact distance, not approximate.
3. Filters reduce candidates below ~10K — pre-filtered subsets may not benefit from global ANN graphs; scan the filtered set instead.
4. You cannot maintain eval infrastructure — ANN without recall@k measurement is guesswork; if you will not measure, do not approximate.
5. Single-vector HNSW is wrong for multi-vector retrieval — Late Interaction Retrieval needs token-level or multi-vector indexes, not one vector per doc on a standard HNSW field.

Prefer managed defaults when ops capacity is limited; prefer self-hosted Faiss/Milvus when you need full control over IVF-PQ and DiskANN parameters.

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.

Related Guides

Concept guides

• Vector Search: The retrieval problem ANN indexes implement.
• Vector Quantization: PQ/SQ codes that IVF-PQ and disk indexes rely on.
• Embeddings: Vector source and metric constraints.
• Vector Databases: Operational systems wrapping ANN.
• Metadata Filtering: Predicates that change ANN behavior.
• Hybrid Search: Dense ANN plus BM25 fusion.
• Late Interaction Retrieval: Multi-vector indexes beyond single-vector HNSW.
• Re-ranking: Precision stage after ANN recall.
• Retrieval Evaluation: Measure recall@k before tuning efSearch.
• RAG: Primary application of ANN-backed retrieval.

Rankings

• Best Vector Databases

Comparisons

• Milvus vs Qdrant · Qdrant vs Pinecone · pgvector vs Pinecone

Tools

• Milvus · Qdrant · Weaviate · Pinecone · pgvector

If you understood this topic, read next:

Diagram: ANN learning path

flowchart LR
    A[Embeddings] --> B[Vector Search]
    B --> C[ANN Indexes]
    C --> D[Quantization]
    D --> E[Eval]

Prerequisites: Embeddings · Vector Search

Next topics: Vector Quantization · Metadata Filtering · Retrieval Evaluation

Interview Questions

1. What is an ANN index and why not use exact search?

   • Expected: sub-linear approximate k-NN; exact is O(nd) and too slow at millions of vectors.

2. How does HNSW search work at a high level?

   • Expected: layered graph, greedy walk from top layer, expand efSearch candidates at layer 0.

3. What do efSearch, M, and nprobe control?

   • Expected: query recall/latency (efSearch, nprobe); graph degree and build quality (M, efConstruction).

4. When would you choose IVF-PQ over HNSW?

   • Expected: billion-scale or tight RAM; accept more tuning and possible rescoring.

5. How do metadata filters interact with HNSW?

   • Expected: post-filter underfill; raise ef or use filtered traversal; measure filtered recall separately.

6. What triggers a full index rebuild?

   • Expected: embedding model change, major corpus replacement, delete churn degrading graph quality.

7. How do you tune ANN parameters in production?

   • Expected: golden query set, exact baseline, sweep efSearch/nprobe until recall@k meets SLO, then load-test.

8. ANN vs late-interaction indexing — what's different?

   • Expected: single vector per doc vs many token vectors; MaxSim aggregation; different storage and index design.

Key Takeaways

• 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 on your corpus — not folklore.
• Filters, updates, and sharding change the winning index; remeasure under realistic predicates.
• Rebuild after embedding model changes; compare engines in Best Vector Databases.

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