Pure in-memory HNSW is excellent for low-latency approximate nearest-neighbor search, but it becomes expensive when the corpus grows to hundreds of millions or billions of dense vectors. A billion 768-dimensional float vectors require roughly three tebibytes for vector payloads alone, and the HNSW graph adds more memory on top. If the application needs high recall over a very large corpus but only moderate query throughput, keeping every vector resident in RAM can be the wrong tradeoff.
HNSW-IF is a hybrid ANN design that keeps only a selected centroid set in an in-memory HNSW graph and stores the larger non-centroid population behind an inverted file. A query first searches the centroid graph to find promising clusters, converts those centroid ids into an inverted-index lookup, retrieves the vectors assigned to those clusters, and reranks the resulting candidates. Vespa’s public billion-scale experiment used this shape to search the SPACEV-1B dataset with most vectors outside the in-memory graph.
The transferable lesson is not specific to one engine: graph search can be used as a routing layer rather than the full index. By making HNSW identify neighborhoods and letting a disk-backed inverted file hold the larger candidate pool, teams can trade query latency for dramatically lower memory pressure while still exposing familiar recall knobs such as number of clusters, pruning thresholds, and reranking depth.
The centroid graph is a smaller HNSW index over representative vectors. In the Vespa design, a fraction of vectors act as centroids and are indexed with ordinary HNSW settings. At query time, the system searches this graph to identify nearby centroids instead of walking through every stored vector.
Each non-centroid vector is assigned to several nearby centroid ids. Those ids become tokens in an inverted file: looking up a centroid id returns the vectors that belong to that neighborhood. Assigning each vector to multiple centroids improves recall because a vector can still be found when the closest route is not the only promising route.
The first phase retrieves candidate ids cheaply; the second phase evaluates vector distance more carefully and reranks the shortlist. Reranking depth is a major quality knob. A larger candidate set costs more I/O and distance computation but can recover true neighbors that would otherwise be missed by centroid pruning.
HNSW-IF keeps HNSW where it is strongest: navigating high-dimensional neighborhoods quickly. The inverted file carries the bulk storage responsibility, so memory scales with centroid count and graph metadata rather than the full vector population.
The index build starts by selecting centroid vectors. Those centroids are inserted into an HNSW graph. For each remaining vector, the system searches the centroid graph and stores the ids of the nearest centroids in an inverted-file field. Vespa’s experiment indexed the twelve closest centroid ids for each non-centroid vector, which means one vector can be retrieved by several centroid neighborhoods.
def build_hnsw_if(vectors, centroid_selector, centroid_fanout):
centroids = centroid_selector(vectors)
graph = HNSW(max_links_per_node=18, neighbors_to_explore_at_insert=100)
inverted_file = defaultdict(list)
for cid, vector in centroids:
graph.insert(cid, vector)
for doc_id, vector in vectors:
if doc_id in centroids:
continue
nearest = graph.search(vector, top_k=centroid_fanout)
for centroid_id, closeness in nearest:
inverted_file[centroid_id].append((doc_id, vector, closeness))
return graph, inverted_fileA query vector is searched against the centroid HNSW graph. The returned centroids are pruned by count or distance threshold, then converted into an inverted-file lookup. The resulting candidate vectors are scored and reranked. In Vespa, the serving layer materializes this as a dot-product query over centroid tokens and then runs a reranking phase over the candidate set.
def search_hnsw_if(query_vector, graph, inverted_file, centroid_k, prune, rerank_k, top_k):
centroid_hits = graph.search(query_vector, top_k=centroid_k)
selected = [
centroid_id for centroid_id, distance in centroid_hits
if distance <= prune
]
candidates = []
for centroid_id in selected:
candidates.extend(inverted_file.get(centroid_id, []))
scored = []
for doc_id, vector, _ in candidates:
scored.append((cosine_distance(query_vector, vector), doc_id))
shortlist = sorted(scored)[:rerank_k]
return exact_or_high_fidelity_rerank(query_vector, shortlist)[:top_k]Vespa implements the pattern with a custom query component that obtains centroids, prunes them, emits a token query against the inverted file, and merges centroid results with the reranked candidate result. A companion document processor assigns each incoming vector to its nearest centroid tokens during ingestion, making the inverted file usable through the same search infrastructure that handles ordinary lexical posting lists.
Some applications need to search enormous embedding corpora but do not need hundreds of thousands of queries per second. Media archives, deduplication systems, catalog discovery, compliance review, and offline candidate generation may tolerate tens of milliseconds of additional latency if the memory bill drops substantially.
Retrieval-augmented generation systems often need broad recall from historical corpora, but only a small set of final passages is sent to a model. HNSW-IF can act as the first-stage candidate generator, with downstream text filters, metadata filters, or neural rerankers applied after the vector shortlist is retrieved.
Search engines already know how to evaluate inverted-index queries, apply attribute filters, and run multi-phase ranking. Encoding centroid membership as inverted-file tokens lets dense vector retrieval participate in the same pipeline as lexical matching, business rules, and result blending.
More centroids produce smaller posting lists and better routing precision, but they enlarge the in-memory graph. Fewer centroids reduce graph memory but force each centroid token to retrieve more candidates. Treat centroid fraction as a capacity-planning decision, not just an accuracy parameter.
A single centroid assignment is fragile around cluster boundaries. Multi-assignment increases index size but gives each vector more chances to appear in the candidate set. The right fanout depends on dimensionality, dataset shape, acceptable write amplification, and recall target.
The centroid search should optimize candidate coverage, while the reranker should optimize final ordering. Keep metrics for both stages: centroid recall tells you whether routing reaches the right neighborhoods, while final recall@k tells you whether reranking returns the correct neighbors.
class HNSWIFQueryPlan:
def __init__(self, centroid_k=128, assignment_fanout=12, prune_threshold=0.6, rerank_k=4000):
self.centroid_k = centroid_k
self.assignment_fanout = assignment_fanout
self.prune_threshold = prune_threshold
self.rerank_k = rerank_k
def estimate_work(self, avg_posting_list):
routed_lists = self.centroid_k
candidate_reads = routed_lists * avg_posting_list
rerank_work = min(candidate_reads, self.rerank_k)
return {"candidate_reads": candidate_reads, "rerank_work": rerank_work}