What is under-exploration in graph search?

Under-exploration in graph search is the failure mode where a search concludes before it has genuinely exhausted the productive avenues available to it — not because the graph lacks the connectivity needed to reach the true answer, and not because the search got misled by a local minimum, but simply because it was allowed to stop too early relative to how much work that specific query actually needed. It’s the most directly and reliably fixable of the failure modes covered in this glossary category, precisely because the underlying graph structure is fine and the search’s own decision-making was reasonable — the problem is purely a matter of insufficient budget.

How does under-exploration actually differ from the other structural failure modes covered elsewhere in this category?

A local minimum, covered on its own glossary page, involves the search’s greedy decision-making genuinely getting stuck at a point where no available next step looks like an improvement, regardless of how much further budget the search might otherwise have had. A missing bridge involves the graph itself lacking a robust path to the correct region, a structural limitation no amount of search budget can overcome. Under-exploration involves neither of these deeper problems — the search was making genuine, steady progress toward better candidates, and simply ran out of budget, tied to efSearch‘s target result-set size, before that progress had fully played out. This is precisely why under-exploration is the failure mode most cleanly and reliably addressed by adjusting a single parameter, since the fix directly targets the actual cause rather than needing to address a deeper structural issue in the graph.

How does this failure mode actually show up in a search trace, and how is that signature distinguished from the others?

A search trace exhibiting under-exploration typically shows the result queue‘s worst entry still improving meaningfully, and the candidate queue still holding genuinely promising unexplored options, right up until the stopping criterion — tied to the current efSearch setting — forces the search to conclude. This is a meaningfully different pattern from a local-minimum or missing-bridge trace, both of which tend to show a search that’s already stopped making real progress well before its stopping criterion technically triggers, or one that concluded normally within a region that simply never contained the answer. An under-exploration trace, by contrast, looks like a search that was still actively succeeding when it got cut off — the diminishing-returns pattern described on the early-termination-in-search glossary page hadn’t yet set in, and continuing further would very likely have kept finding closer, genuinely better candidates.

Why would a search actually be under-exploring in the first place, given that efSearch is a deliberately chosen setting rather than an accident?

Under-exploration most commonly arises when a single, fixed efSearch value gets applied uniformly across an entire workload whose queries actually vary considerably in difficulty, as covered on the query-difficulty glossary page. An efSearch setting that’s perfectly adequate for typical, easy queries can leave genuinely harder queries — ones landing in a region with high local intrinsic dimensionality, or ones affected by query-database distribution shift — under-explored, since those harder queries would need meaningfully more search budget to reach the same recall a typical query achieves comfortably. This is exactly the scenario adaptive-ef and query-adaptive-exploration techniques, covered on their own glossary pages, are designed to address: rather than accepting under-exploration on the workload’s hardest queries as an unavoidable cost of keeping efSearch low enough to serve easy queries efficiently, these techniques identify harder queries and grant them additional search budget specifically, rather than applying one fixed setting uniformly regardless of actual difficulty.

Does simply raising efSearch across the board always resolve under-exploration cleanly, with no other consequence to consider?

Raising efSearch does directly address under-exploration by definition, since it’s precisely the parameter controlling how much search budget every query receives — but doing so uniformly across an entire workload means paying that increased cost on every single query, including the easy ones that were already achieving strong recall at the original setting and gain little to nothing from the additional budget. This is exactly why a uniform efSearch increase, while it reliably fixes under-exploration wherever it exists, isn’t necessarily the most efficient fix available — the adaptive techniques mentioned above exist specifically to target the increased budget only where it’s actually needed, rather than spending it uniformly across a workload where most queries didn’t need the extra help in the first place.

Having covered under-exploration as the most directly fixable of the failure modes covered in this category, the efSearch and search-trace glossary pages are worth revisiting together with this fuller picture of exactly how this specific failure signature gets identified and addressed. From there, the adaptive-ef and query-adaptive-exploration glossary pages pick up the more targeted, efficient response to under-exploration, addressing it selectively rather than through a blanket parameter increase applied to an entire workload.