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.

5What happens to recall

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 most runs measured so far, the collaborative search returns the same results an ordinary Lucene search returns; the deepest single-process setting, k = 10,000, gave up 0.02 to 0.04 of recall against the full-depth baseline (section 6). 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 right baseline 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.

9Alternative approach in research: the Turbovec approach

Everything above accepts HNSW as the substrate and works around its nature: the floor has to be guarded by a gate and a dial because a graph walk can be starved of the low-scoring bridge nodes it navigates through. A second line of research, earlier than this one, changes the substrate instead. Turbovec is a quantized exhaustive-scan index: two to four bits per dimension, SIMD kernels, every vector compared on every query. On a single machine that sounds like the expensive way around. Distributed, it removes the two hardest problems on this page.

First, the floor loses its caveats. A scan that prunes on the floor skips work, never reachability - every vector still gets the block-level compare - so the validity lemma applies with no ascent gate, no greediness dial, and no small-k switch-off. Recall parity stops being an empirical result to defend across corpora and becomes the boring kind of true: a floor-seeded scan returns exactly what the unseeded scan returns whenever the seed is a true lower bound. The kernel already tracks the running k-th best with a SIMD block prefilter, so seeding it is a parameter, not a collector decorator.

Second, scores compare across shards. Turbovec's rotation and codebooks are corpus-independent; the one data-dependent piece is a calibration fitted on the first batch of vectors. Pin that calibration across shards and the same vector scores identically wherever it lives, so the coordinator's merge is exact. The distributed-statistics problem that lexical scoring never escapes is simply not there.

Exactness changes the fan-in arithmetic from section 3 as well. The static quota needs its λ-margin because it is an estimate of what a shard might owe; a converged floor is a bound, not an estimate, so each shard ships exactly the results that survive it:

Where the floor's savings land

The floor acts on a different term here than it does for HNSW, and the split is worth writing down. A shard's query time is a scan term plus a selection term. The scan term is fixed - every vector is compared, which is the recall guarantee and the cost floor in one - and it is memory-bandwidth bound, so it is small and predictable: at two bits per dimension the whole shard streams through the SIMD kernels at whatever the machine's bandwidth allows. The selection term is where a search actually spends its time at deep k, and it is the term the floor cuts.

The two turbovec issues attack this same term from both sides: the floor shrinks I, the large-k selection path shrinks c(k). Either alone helps; together the selection term stops mattering and the shard runs at the speed of its memory bus.

The scout gets simpler too. Turbovec is already the quantized in-memory sample the scout was built from, so the scout stops being a special component and becomes a small index like the others.

Nothing limits Turbovec to one machine - a gRPC surface exists and the scatter-gather design above transfers directly, guards removed - but so far the measurements are single-node only. The cost of the floor travelling between busy machines is the same open question it is for HNSW, and deep-k selection inside the kernel currently degrades past k in the low thousands. Three upstream issues carry the design conversation: calibration seeding, a seedable search cutoff, and the large-k selection path; the first two have working implementations with tests. The trade is explicit: give up the graph's sublinear visit counts on a single node in exchange for a bound that holds without guards and scores that merge without correction. Whether that trade wins at cluster scale is exactly what the distributed benchmark in section 8 has to show - for both substrates.

10Read 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.