Billions of vectors turn HNSW tuning into a memory problem first. Learn how to balance recall, latency, filters, and build cost at scale. Read now.
Memory Is the First Constraint
At billion scale, HNSW stops being primarily a graph-tuning problem and becomes a memory-layout problem. Each vector, each neighbor list, and each layer of the hierarchical graph must live somewhere the search path can reach quickly. If the full graph and embeddings do not fit in RAM, you pay in paging, shard fan-out, or remote fetches long before you exhaust CPU. Design around a hard memory budget first: decide how much resident capacity you can afford per node, then back into graph degree, layer policy, and whether vectors stay full-precision or compressed.
Practical levers are blunt but effective. Cap the maximum degree so neighbor lists stay short. Prefer compact edge encodings over verbose adjacency structures. Keep hot layers and entry-point neighborhoods co-located. When memory still overflows, quantize vectors or store full-precision data on a colder tier and keep only what the walk needs in memory. Every extra byte per node multiplies across billions of points.
Balance Recall, Latency, and Graph Density
HNSW quality is governed by how richly the graph connects points and how hard you search it. Higher construction connectivity and larger candidate lists at build time produce more robust neighborhoods and better recall, but they inflate index size and build duration. At query time, expanding the candidate beam improves recall at the cost of more distance computations and higher tail latency. There is no universal sweet spot—only a surface you must sample against your own data distribution and SLOs.
Treat tuning as a closed loop. Fix a memory envelope, then vary construction connectivity and query beam width while measuring recall at a fixed latency budget (or latency at a fixed recall target). Prefer the smallest graph and the leanest query settings that still clear your bar. Overbuilding the graph “just in case” is expensive at this scale; underbuilding forces you to run wider queries forever.
Filters Change the Search Path
Metadata filters break the assumption that every neighbor is a valid candidate. When a large fraction of edges point to points that fail the filter, the walk stalls, recall drops, or latency spikes as the engine explores around blocked regions. Pre-filtering (apply predicates before graph walk) and post-filtering (walk first, then drop invalid hits) both fail in different regimes: sparse filters waste work on dead edges; aggressive post-filters may return too few valid results.
- Partition or shard by high-cardinality filter keys when queries almost always constrain those keys.
- Maintain filter-aware candidate expansion so the beam keeps filling with valid neighbors instead of stalling on rejected ones.
- Budget extra search width for selective filters rather than assuming unfiltered parameters still hold.
Validate filter paths with the same rigor as pure ANN: measure recall and latency under realistic predicate selectivity, not only on unfiltered benchmarks.
Control Build Cost Before You Scale Out
Building an HNSW index over billions of vectors is a multi-pass, neighbor-search-heavy job. Construction cost scales with graph density, candidate list size, and how often you reinsert or rebuild as data grows. Incremental inserts are convenient but can degrade structure over time if deletes and updates accumulate without compaction. Full rebuilds restore quality but demand planned windows, temporary capacity, and a cutover strategy that does not interrupt serving.
Keep build cost predictable by staging inserts in batches, monitoring graph quality metrics as the index grows, and scheduling rebuilds before search degrades rather than after. If memory or build time forces a split, prefer sharding strategies that preserve local graph quality inside each shard and keep cross-shard fan-out bounded. At this scale, the index you can rebuild and fit in memory under load is more valuable than a theoretically denser graph you cannot afford to maintain.