Collaborative shared-floor distributed HNSW search

1The waste in distributed vector search

HNSW gives good approximate nearest-neighbour recall on a single node. Splitting the index across shards is where the cost comes back. The common contract asks every shard for a full local top-k, ships all of it to a coordinator, and merges. The coordinator keeps k results out of the k·s it received and discards the rest.

At sixteen shards and k = 10,000 that is 160,000 candidates computed and shipped so that 10,000 can be kept. The other 150,000, about 94 percent, are wasted. It gets worse as k and the shard count grow. The reason is simple: nothing tells a running search that the rest of the cluster already holds better results than the ones it is still chasing. Each shard searches as if it were alone.

2The mechanism: one shared number

The whole idea is a single per-query scalar called the global floor. It is the k-th best similarity among every hit seen so far across every shard, held in a bounded min-heap of size k. Because the hits seen so far are always a subset of the hits that will ever exist, the k-th best of the subset can never sit above the k-th best of the whole. The floor is therefore a lower bound on the final cutoff, and it only rises.

HNSW already has the hook this needs. Its graph walk keeps re-reading a minimum competitive similarity from the collector after each accepted hit and stops when it can no longer clear that bar. A thin decorator that folds the shared floor into that value raises the bar through machinery that is already there. The graph search code itself is not touched. That is the entire footprint of the idea inside Lucene: a floor object, one method to push an externally computed bound in, and a collector decorator that reads it.

3How much less work, in principle

There are two separate savings. The first does not even need the floor. If shards are random samples of the corpus, which hash or round-robin sharding both give, then the number of true global top-k hits that land in a shard holding a fraction p of the data follows a binomial distribution with mean k·p. A shard almost never owes more than a little above that mean, so each shard can be asked for a quota rather than the full k:

For s equal shards, where p = 1/s, the quotas add up to a total that grows with the square root of the shard count rather than linearly:

Compared against the old "every shard returns k" contract, the fan-in shrinks by

The limit is the point worth sitting with. The large-k case that hurts most today is exactly where the reduction approaches the full s-fold. At sixteen shards, using the integer quotas the code actually computes:

The second saving is the floor itself, and it acts on a different quantity. Fan-in is about how many results cross the wire. The floor is about how many vectors each shard has to compare on the way to its results. The visit count of an HNSW search splits into a small graph-descent term and a term proportional to the exploration width, and on the measured corpus the width term is about 99 percent of the visits:

Because that term dominates, cutting how far each shard explores translates almost directly into fewer comparisons. A converged floor lets a shard stop refining once it can prove the rest cannot beat what the cluster already holds, and under random sharding only about one in s of a shard's results survive the merge anyway, so most of that refinement was destined for the bin. The catch, and it is a real one, is the word converged. The floor only helps to the extent it has risen while the search is still running.

4The scout: a floor that arrives early

A floor that only reaches its useful value at the end of the search saves nothing, because by then every shard has already done the work. The floor has to be high while searches are still deciding what to explore. That is what the scout is for.

The scout is one extra shard that holds a small in-memory sample of the whole corpus, quantized so it is cheap to search. It is searched at the same time as the real shards, not before them, but because it is small and in memory it finishes first and merges its results first. The mental model is a cache. A cache does not sit in a separate phase ahead of the database; it answers in parallel and simply returns sooner, and its answer shapes what the slower path does next. The scout is a cache for the floor.

Why a sample seeds a tight floor

The reason the scout can seed a useful floor from a sample, rather than a weak one, is a ranking argument. Suppose the scout holds a fraction ρ of the corpus, drawn uniformly. Ask it for its own top-k. Its k-th result sits, in expectation, at the position in the full corpus where k of the sampled points fall above it, which is global rank k/ρ:

Now set ρ = 1/s, a sample the size of one shard. The scout's floor lands at global rank k·s. That is the same score a real shard only advertises once it has fully converged and knows its share of the global answer. In other words, at the very start of the search the scout hands the cluster a floor as tight as the one it would otherwise have to wait for every shard to finish to obtain. The tighter the floor early, the more exploration the real shards can skip. The scout's own top results are re-scored in full precision before they set the floor, so the quantization that makes it fast never makes the bound invalid, and no calibration constant is needed.

Whether this holds up outside the derivation is one of the things that still needs measuring, particularly when the sample is not a clean uniform draw.

5Recall, honestly

The floor validity lemma protects the answer only against pruning candidates whose current frontier score is already below the floor. HNSW is a greedy approximation to begin with, and a stock search can still reach a good cluster through a low-scoring bridge node. Raising the bar toward the true cutoff prunes in exactly the band where those bridges live. So the design is not recall-safe by construction. It is the same greedy approximation stock HNSW already makes, at a tighter bar, with two explicit guards to keep the tighter bar from costing recall.

The first guard is an ascent gate: a shard ignores the global floor until it has collected enough of its own hits to have reached its query's neighbourhood, so the bound never applies before the search has arrived where it is going. The second is a greediness dial g. At g = 0 the collector is bit-for-bit identical to stock search and the floor has no effect. At the default of 0.5 the effective bar can never rise past a fixed fraction of what the shard has already seen, so a fixed depth of exploration always survives. Below a small k the mechanism switches itself off entirely and runs the plain collector, because the savings grow with k while the risk to recall concentrates at small k.

The important claim is the modest one. In the runs measured so far, the collaborative search returns the same results an ordinary Lucene search returns. Recall does not improve, and it is not meant to. It holds at the level Lucene already produces while the search does less work to get there. Any suggestion of perfect or near-perfect recall would be wrong: HNSW is approximate, the baseline is approximate, and the goal is to match the baseline, not to exceed it. Recall parity is an empirical result on specific corpora and specific settings, not a theorem, and it needs to be shown across more of them.

6What has been measured

Two kinds of measurement exist so far. Neither is the real thing, which is separate machines under load, and both are reported as direction, not proof.

Single process standing in for a cluster

On 247 million Cohere embeddings, 1024 dimensions, dot product, sharded round-robin into sixteen and joined so that one Lucene segment stands in for one remote shard, the floor is measured against the two baselines that matter. Against the wasteful distributed contract, where every shard returns a full k and the coordinator merges, the floor cuts vector comparisons by about 24 percent at k = 1,000 while recall moves by 0.003, and by roughly 88 to 91 percent at k = 10,000 at a recall cost of 0.02 to 0.04. Against a single JVM's own optimistic multi-segment search, which already avoids most of the redundant work inside one process, the gain is only low single digits. That second comparison is the honest one for a single machine, and it is the reason this belongs in the sandbox rather than the core: inside one process, Lucene already does most of what the floor would do.

A real, if small, cluster

A nine-node cluster, one fast workstation and eight Raspberry Pi 5 boards, was run less to produce a headline number than to watch the floor behave on slow, staggered nodes, which is precisely the setting the single-process harness cannot show. There the scout configuration, with the fast node seeding the floor first, cut visits by roughly 53 to 58 percent at k from 50 to 1,000, tapering to about 38 percent at k = 5,000, and the collaborative run returned the same result set as the standard run at every tested point. That last part is the recall result, and it is a parity result: same answers, less work, not better answers. It is the clearest evidence so far that the floor arrives early enough to matter when nodes are slow, and it is still a small cluster on a bench, not a benchmark to lean on.

7What makes it distributed

The Lucene collector is only the in-process primitive: the floor object and one method to push a bound in from outside. Everything that turns it into a distributed search lives in the reference engine. A shard runs its Lucene search as a server stream, emitting each accepted hit as it is found rather than waiting for a final top-k. A second, bidirectional stream carries floor updates: the shard pushes its local contribution up, the coordinator pushes the global floor back down, and because floor updates are a monotone maximum they are safe to apply out of order or more than once, with no sequence numbers. The coordinator merges over distinct global document ids, which is where the lemma's requirement that advertised scores come from real, distinct hits is enforced. Cluster membership, shard routing by stable hash, and per-peer channel reuse round out the engine. The per-shard quota from section 3 is applied here too, independently of the floor, so the fan-in reduction and the exploration reduction stack.

The same shared-floor idea has also been extended to block-join vector search, where results are parent documents scored by their best child, by tracking the floor over parents rather than raw child scores. That extension lives in Lucene's join module. Across all of it, nothing in Lucene's core is changed.

9Read the work

The Lucene collector, its tests, and the block-join extension are in PR #16357. The distributed engine, the coordination protocol, and the benchmark harness are in distributed-search. The broader research context, including this work and the pipelines around it, is on the research page.