What is a search failure mode?

A search failure mode is a specific, identifiable pattern by which an HNSW search ends up missing a genuinely correct result — a named category of root cause, distinct from the general observation that recall fell short, that describes mechanically why a particular query didn’t find what an exact search would have found. Naming these patterns explicitly turns an otherwise vague symptom, “this query’s recall was low,” into a specific, diagnosable condition with its own characteristic signature, which is exactly what makes systematic debugging of recall problems possible rather than relying on guesswork.

What are the main distinct failure modes that account for most real HNSW recall shortfalls?

A local minimum in graph search, covered on its own glossary page, is perhaps the most fundamental failure mode: a greedy traversal stops at a node whose every neighbor looks farther from the query than the node itself, even though a genuinely closer point exists reachable only through a path the search never took. A missing bridge in graph connectivity, covered under this same glossary category, describes a structurally different failure: a query’s true nearest neighbors sit in a region of the graph that’s only weakly, fragilely connected to wherever the search actually starts, making the correct answer effectively unreachable regardless of how the search’s parameters are tuned. Insufficient exploration is a third distinct pattern, arising when efSearch is simply set too low for a given query’s actual difficulty, causing the search to conclude before it had genuinely exhausted the productive paths available to it — this is the one failure mode most directly and reliably fixable by turning up a search parameter, since it isn’t really a structural problem with the graph at all, just a case of the search not being given enough budget to succeed.

Why does it matter to distinguish these failure modes from each other, rather than treating every recall shortfall as the same generic problem?

Each failure mode calls for a genuinely different response, and applying the wrong one wastes effort without fixing the actual underlying issue. Insufficient exploration responds directly and reliably to a larger efSearch, since the problem really was just a matter of search budget. A local minimum caused by a poorly diversified graph doesn’t respond nearly as well to a larger efSearch alone, since the fundamental issue is the graph’s own connectivity rather than how much of it gets explored — this calls instead for reconsidering construction parameters like efConstruction or M, or investigating whether the neighbor-selection heuristic is actually behaving as intended for the specific region of the data involved. A missing bridge is often the hardest of the three to fix through parameter tuning alone, since it reflects a genuine structural gap in the graph that might require targeted reconstruction of the affected region, or accepting that region’s recall limitation, rather than any global parameter adjustment reliably resolving it. Misdiagnosing which failure mode is actually occurring — turning up efSearch in response to what’s really a missing-bridge problem, for instance — can waste considerable tuning effort chasing a fix that was never going to address the real cause.

How does someone actually go about determining which failure mode is responsible for a specific query’s poor recall?

A search trace, covered on its own glossary page, is the primary diagnostic tool here — examining exactly which nodes a problematic query’s search actually visited, in what order, and how the candidate and result queues evolved, generally reveals which of these failure modes is actually at play. A trace showing the search settling early, well before efSearch’s target size was reached, with the candidate queue exhausted prematurely, points toward a local minimum or a missing bridge rather than insufficient exploration. A trace showing the search still actively finding closer candidates right up until efSearch’s target size forced it to conclude points more directly toward insufficient exploration, suggesting a larger efSearch might genuinely help. Comparing a trace from the problematic query against a trace from a similar, well-behaved query, as suggested on the search-trace glossary page, is often the most direct way to spot exactly where and how the two diverged.

Are these three failure modes the complete list, or do other patterns exist beyond them?

These three represent the most commonly discussed and most directly actionable failure modes, but they aren’t an exhaustive taxonomy of every conceivable way a search could underperform — query-database distribution shift and out-of-distribution queries, covered on their own glossary pages, describe a related but distinct family of causes rooted in data distribution rather than graph structure or search parameters per se, and specific implementation bugs, incorrect distance-function configuration, or data quality issues can all produce recall problems that don’t map cleanly onto any of these named structural patterns at all. The three covered here are best understood as the most common, most structurally interesting failure modes worth knowing by name, rather than a claim that no other cause of poor recall could ever exist.

Having covered the main structural failure modes behind recall shortfalls and why distinguishing them actually matters for effective tuning, the local-minimum-in-graph-search and missing-bridge-in-graph-connectivity glossary pages are worth revisiting together with this fuller picture of how they relate to each other and to insufficient exploration. From there, the search-trace glossary page is the natural next stop for the practical diagnostic method actually used to tell these failure modes apart in a real, specific case.