HNSW vs IVFFlat Algorithm Selection

pgvector ships two Approximate Nearest Neighbor (ANN) index types — Hierarchical Navigable Small World (HNSW) and Inverted File with Flat compression (IVFFlat) — and the choice between them is the single decision that most constrains your vector search deployment. Pick the wrong one and the symptoms are quiet but expensive: recall silently drifts below your service-level target, index builds miss their maintenance window, maintenance_work_mem spills to disk, or a busy ingestion stream stalls behind an exclusive lock. This page gives search platform engineers, AI/ML teams, and Python data-pipeline builders a parameter-level decision framework — grounded in memory math, build cost, write amplification, and recall behaviour — plus runnable SQL and Python to validate the choice before it reaches production. It sits under the broader HNSW & IVFFlat index creation and tuning reference; read that first if you need the end-to-end lifecycle rather than just the selection question.

Architectural Divergence & Trade-offs #

HNSW builds a multi-layer proximity graph. Every vector becomes a node with up to m bidirectional edges to its nearest neighbours on the base layer, and a logarithmically thinning set of nodes is promoted into higher “express lane” layers. A search enters at the top layer, greedily walks toward the query vector, and descends layer by layer, giving roughly O(log N) hops to reach a good candidate set. That structure is why HNSW delivers consistent single-digit-to-tens-of-milliseconds latency even at high query volume — but it also means the entire graph, including all edge lists, must live in memory to search efficiently, and construction is comparatively expensive because each insert re-searches the graph to place its edges.

IVFFlat takes the opposite approach. A one-time k-means pass partitions the vector space into lists centroids (Voronoi cells). Each vector is assigned to its nearest centroid, and a query scans only the probes closest cells rather than the whole table. Storage is flat — the raw vectors sit in inverted lists with no graph overhead — so the index is dramatically smaller and faster to build. The cost is recall sensitivity: a query vector near a cell boundary can have true neighbours sitting just across the border in an unscanned list, so recall depends entirely on scanning enough probes, and that pushes latency back up.

The trade-off reduces to graph traversal versus partitioned bucket scanning. HNSW spends memory and build time to buy low-latency, high-recall reads. IVFFlat spends recall headroom and query-time probes tuning to buy a small footprint and cheap, fast builds. Neither is universally correct; the right answer is a function of your read/write ratio, dataset size, memory budget, and recall SLA. Because the index is bound to exactly one distance operator class (vector_cosine_ops, vector_l2_ops, or vector_ip_ops), that decision is upstream of algorithm choice — settle the metric first using cosine vs L2 distance metrics, because a mismatched operator makes the planner ignore either index type entirely.

Storage and memory reality #

The graph is the reason HNSW memory planning matters. Beyond the raw 4 * d + 8 bytes per single-precision vector(d) row, HNSW adds roughly m edge references per node on the base layer (plus the sparser upper layers), so a high m on a high-dimensional column can more than double resident size. The full per-row accounting — column width, TOAST thresholds, and index amplification — is worked through in pgvector storage overhead analysis, and if that math pushes you over budget, switching the column to halfvec via vector data type selection halves the vector payload before you even choose an algorithm.

Parameter Space & Diagnostic Workflow #

The two algorithms expose disjoint tuning knobs, and confusing build-time with query-time parameters is the most common source of wasted tuning cycles.

HNSW has two immutable build-time parameters — m (max edges per node) and ef_construction (candidate list size during build) — and one mutable query-time parameter, ef_search (candidate list size during search). Only ef_search can be changed without rebuilding, so it is your live recall/latency dial. IVFFlat has one build-time parameter, lists (number of centroids), and one query-time parameter, probes (cells scanned per query). Both ef_search and probes are set per session with SET LOCAL, which lets you route different query classes at different recall levels against the same index.

The diagnostic loop is identical in shape for both: hold the build parameters, sweep the query-time parameter, and watch where recall stops improving. The knee of that curve is your production setting — anything past it just adds latency. For the deeper calibration methodology behind m and ef_construction (including recall-vs-build-time surfaces), work through optimizing m and ef_construction parameters.

-- HNSW: sweep the query-time dial without touching the index
SET LOCAL hnsw.ef_search = 40;
EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM document_embeddings
ORDER BY embedding <=> '[...]'::vector(768)
LIMIT 10;

-- IVFFlat: same idea, different knob
SET LOCAL ivfflat.probes = 10;
EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM document_embeddings
ORDER BY embedding <=> '[...]'::vector(768)
LIMIT 10;

The lists = sqrt(N) rule deserves emphasis because getting it wrong is the classic IVFFlat failure. With N = 1,000,000 vectors, sqrt(N) is 1,000 lists; each list then holds ~1,000 vectors, and scanning a handful of probes stays cheap. Under-provision to lists = 100 and each cell balloons to 10,000 vectors, so every probe degrades toward a partial sequential scan and query time collapses.

Step-by-Step Implementation #

The following sequence takes a workload profile to a validated production index. It assumes a table already modelled with an explicit vector(d) column and the correct operator class.

1. Establish the table and operator class #

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE document_embeddings (
    id          BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    tenant_id   UUID NOT NULL,
    embedding   vector(768) NOT NULL,
    created_at  TIMESTAMPTZ DEFAULT now()
);

2. Size the build, then create the index #

For HNSW, provision maintenance_work_mem generously (25% of RAM is a good starting point, capped near 32 GB) and build concurrently so writes are not blocked:

SET maintenance_work_mem = '8GB';

CREATE INDEX CONCURRENTLY idx_docs_hnsw
ON document_embeddings
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 128);

For IVFFlat, the critical prerequisite is that the table already holds a representative sample of rows — k-means needs real data to place centroids, so building on an empty or tiny table produces useless partitions:

-- lists ≈ sqrt(N); here N ≈ 1,000,000
CREATE INDEX idx_docs_ivf
ON document_embeddings
USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 1000);

Note that ivfflat does not benefit from CONCURRENTLY the way HNSW does — its build is a fast single pass — but for very large tables the pipeline-aware patterns in asynchronous index build strategies keep the build off the critical write path regardless of algorithm.

3. Set the query-time defaults #

Bake sensible session defaults into your connection pool’s options or a per-request SET LOCAL, so every query enters the index at the recall level you validated:

-- HNSW
SET LOCAL hnsw.ef_search = 64;
-- or, IVFFlat
SET LOCAL ivfflat.probes = 12;

For a fully worked HNSW build — schema validation, memory sizing, concurrent build monitoring, and lifecycle — follow the step-by-step HNSW index creation for production workloads walkthrough, which is the long-form companion to this decision page.

Validation & Recall Testing #

Selecting an algorithm is meaningless without measuring what recall it actually delivers on your data. Recall@K is the fraction of the true top-K neighbours (computed by exact brute-force search) that the approximate index returns. Never promote an index without this number.

First, confirm the planner is actually using the index and not silently falling back to a sequential scan:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id
FROM document_embeddings
ORDER BY embedding <=> '[...]'::vector(768)
LIMIT 10;
-- want: "Index Scan using idx_docs_hnsw"
-- red flag: "Seq Scan on document_embeddings"

Then measure recall against exact ground truth. The exact answer comes from the same distance operator with the index disabled, so you compare like with like:

import psycopg
import numpy as np

def recall_at_k(conn, query_vecs, k=10):
    hits = 0
    for q in query_vecs:
        lit = "[" + ",".join(f"{x:.6f}" for x in q) + "]"
        with conn.cursor() as cur:
            # exact ground truth: force a sequential scan
            cur.execute("SET LOCAL enable_indexscan = off")
            cur.execute(
                "SELECT id FROM document_embeddings "
                "ORDER BY embedding <=> %s::vector LIMIT %s", (lit, k))
            truth = {r[0] for r in cur.fetchall()}
        with conn.cursor() as cur:
            # approximate: index-served
            cur.execute("SET LOCAL hnsw.ef_search = 64")
            cur.execute(
                "SELECT id FROM document_embeddings "
                "ORDER BY embedding <=> %s::vector LIMIT %s", (lit, k))
            got = {r[0] for r in cur.fetchall()}
        hits += len(truth & got) / k
    return hits / len(query_vecs)

with psycopg.connect("dbname=vectors") as conn:
    sample = np.load("query_sample.npy")   # a few hundred representative queries
    print("recall@10:", recall_at_k(conn, sample))

Run this sweep at several ef_search (HNSW) or probes (IVFFlat) values and plot recall against measured p95 latency. The production setting is the smallest knob value that clears your recall SLA — typically the knee where the curve flattens. Wire this same routine into CI as a regression gate so a model swap or a parameter change that quietly drops recall fails the build instead of shipping. Categorising the failures this surfaces — dimension mismatch, operator drift, spill-to-disk — is covered in index validation and error categorization.

Failure Modes & Gotchas #

• Silent sequential-scan fallback. If the query operator does not match the index operator class (an <-> L2 query against a vector_cosine_ops index), or planner statistics are stale after a bulk load, PostgreSQL abandons the index without error. Run ANALYZE document_embeddings; after every large load and confirm an Index Scan node in EXPLAIN.
• IVFFlat recall collapse from bad lists. Building on a near-empty table, or setting lists far from sqrt(N), yields lopsided cells. Recall looks fine in staging on 10k rows and craters in production at 10M. Always build IVFFlat on a representative row count and re-evaluate lists when the table grows an order of magnitude.
• HNSW build OOM / spill. A large ef_construction on a high-dimensional column can exceed maintenance_work_mem and spill to disk, stretching a 20-minute build into hours. Size memory to the build, or lower ef_construction and raise ef_search at query time to recover recall.
• Centroid drift in IVFFlat. Centroids are frozen at build time. As the embedding distribution shifts (new content domains, a model upgrade), the partitions stop reflecting the data and recall decays. Schedule periodic REINDEX on IVFFlat indexes; HNSW graphs degrade more gracefully but still accumulate dead edges under heavy UPDATE/DELETE.
• WAL pressure from HNSW writes. Because inserts mutate graph edges, HNSW generates substantially more WAL than IVFFlat under a write-heavy stream — the trap behind replication lag and checkpoint spikes during bulk upserts. If ingestion is your bottleneck, that write amplification alone can decide the choice in IVFFlat’s favour.
• Immutable parameters treated as tunable. m, ef_construction, and lists cannot be changed in place — altering them means a full rebuild. Only ef_search and probes are live. Teams that discover this mid-incident lose a maintenance window they did not plan for.

Monitoring & Alerting Hooks #

Instrument the index the moment it goes live. The highest-signal check is the ratio of index scans to sequential scans on the vector table — a rising seq_scan count is the earliest sign of a fallback:

SELECT
    relname,
    idx_scan,
    seq_scan,
    idx_tup_fetch,
    n_dead_tup
FROM pg_stat_user_tables
WHERE relname = 'document_embeddings';

-- per-index usage and read volume
SELECT indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
WHERE relname = 'document_embeddings';

Track build progress on long concurrent HNSW builds so a stalled worker pages someone before the window closes:

SELECT phase, blocks_done, blocks_total,
       tuples_done, tuples_total
FROM pg_stat_progress_create_index;

For a Prometheus-compatible scrape, expose the fallback ratio and dead-tuple ratio as gauges via postgres_exporter custom queries, and alert on them:

-- exporter query: sequential-scan fallback ratio for vector tables
SELECT relname,
       seq_scan::float / NULLIF(seq_scan + idx_scan, 0) AS seq_scan_ratio,
       n_dead_tup::float / NULLIF(n_live_tup, 0)        AS dead_tuple_ratio
FROM pg_stat_user_tables
WHERE relname = 'document_embeddings';

Alert when seq_scan_ratio climbs above a few percent (an index the planner has abandoned) or dead_tuple_ratio exceeds ~0.15 (time to REINDEX CONCURRENTLY). Pair this with the recall regression gate from the validation section, and treat a failed recall check as a page-worthy event — it is the one degradation that database-level metrics cannot see. For write-path auditing on multi-tenant tables, pgaudit on the vector table records which tenant or job triggered a rebuild, complementing the isolation controls in security boundaries for vector data.

Selection Matrix & Production Guardrails #

Consult the official PostgreSQL index documentation for planner behaviour and the pgvector repository for algorithm-specific release notes and known limits. The durable rule: default to HNSW for read-heavy semantic search with a recall SLA, and reach for IVFFlat only when memory ceilings or write throughput make the graph untenable — then validate the choice with the recall harness above before it carries production traffic.

FAQ #

Related #

• Optimizing m and ef_construction Parameters — calibrate the HNSW build knobs once you have chosen the graph.
• Asynchronous Index Build Strategies — keep either index build off the critical write path.
• Index Validation & Error Categorization — classify the recall and fallback failures this page’s harness surfaces.
• Step-by-Step HNSW Index Creation for Production Workloads — the long-form build companion to this decision guide.
• Vector Data Type Selection — switch to halfvec to shrink the footprint before choosing an algorithm.

Up: HNSW & IVFFlat Index Creation & Tuning