What is query-database distribution shift?

Query-database distribution shift describes a situation where the queries a search system actually receives don’t follow the same statistical distribution as the vectors that were indexed to answer them — queries tend to land in different regions of the embedding space, or with different density patterns, than the database vectors do. This might sound like a subtle statistical technicality, but it has a direct, practical consequence for HNSW: the graph‘s structure and its search behavior were shaped entirely by where the database vectors sit, so when queries systematically land somewhere the graph wasn’t built to handle well, search quality can suffer in ways that have nothing to do with how well the index was tuned.

Why would queries and the indexed data ever follow different distributions in the first place?

It’s tempting to assume that queries are just more examples drawn from the same underlying population as the indexed data, but in most real applications, that assumption doesn’t actually hold. A product catalog’s embeddings might be evenly distributed across every category a store sells, while real user search queries concentrate heavily on a small number of popular categories, rarely touching the long tail of niche items that still make up a large fraction of the indexed vectors. A document retrieval system might index a broad, general corpus, while the questions users actually ask cluster around a narrower set of topics that happen to be currently relevant or popular. In both cases, the queries and the database vectors are genuinely drawn from different underlying processes — one reflecting what exists in the catalog or corpus, the other reflecting what people actually want to find — and there’s no reason to expect those two processes to produce the same statistical distribution over the embedding space just because they happen to live in the same coordinate system.

This kind of mismatch is especially likely whenever the entity generating queries and the entity generating the indexed data are fundamentally different things — real users typing search terms versus a fixed catalog of products, for instance — since there’s no structural reason for a user’s search behavior to mirror the composition of whatever inventory happens to be indexed.

How does this mismatch actually translate into a problem for HNSW’s search quality?

HNSW‘s graph is built entirely from the database vectors — every edge, every layer assignment, every neighbor-selection decision during construction is based purely on the relationships between indexed points, with no input at all from what future queries might look like. If queries reliably land in regions where database vectors are dense and well-connected, the graph the construction process built naturally supports fast, accurate search there, since that’s exactly the kind of region the neighbor-selection heuristic had plenty of good candidate connections to work with. But if queries systematically land in a sparser region of the embedding space — one where fewer database vectors exist to have formed a well-connected local neighborhood in the first place — the graph in that region may simply be thinner and less thoroughly explored during construction, making it a genuinely harder region for a greedy search to navigate accurately, independent of any parameter tuning applied globally to the index.

This connects directly to the query difficulty and local intrinsic dimensionality concepts covered elsewhere in this documentation, but it’s worth distinguishing as its own specific cause: local intrinsic dimensionality describes a query being hard because of the geometric complexity of its neighborhood, while query-database distribution shift describes queries being hard, in aggregate and predictably, because of a systematic mismatch between where queries tend to land and where the indexed data actually provides good graph structure to search through. The former is a property of individual query locations; the latter is a property of the entire workload, and it can affect recall in a directionally biased, entirely predictable way rather than the query-to-query variation local intrinsic dimensionality describes.

What can actually be done about a mismatch like this in practice?

Recognizing that this kind of shift exists is the first and most important step, since it reframes a recall problem that might otherwise look like a mysterious, unpredictable tuning issue into something with an identifiable, structural cause. Once identified, a few practical responses become available: evaluating an index using a benchmark set of queries drawn from the real query distribution, rather than from the indexed data itself, gives a far more honest picture of production recall than benchmarking with queries sampled from the database, which can look deceptively strong precisely because those “queries” are exactly the kind of points the graph was built to handle well. Beyond evaluation, some systems address a known, persistent shift by deliberately over-representing the query-heavy regions during index construction or by tuning search parameters differently depending on which region of the space a given query falls into, rather than relying on a single global efSearch setting to serve a workload whose difficulty varies systematically rather than randomly across the space.

Having covered why the queries a system actually receives can behave quite differently from the data it was built to search, the out-of-distribution query and in-distribution query glossary pages are the natural next stop, since they describe the specific, individual-query version of exactly this same underlying concern. From there, the query difficulty and adaptive ef entries, under recall and query difficulty, look at how a search system can respond to uneven difficulty across a workload, whether that difficulty stems from local geometry, distribution shift, or some combination of both.