What is filtered nearest-neighbor search?

Filtered nearest-neighbor search is nearest-neighbor search combined with an additional, non-vector condition results must also satisfy, such as belonging to a category or falling within a price range.
Created: Updated: 5 min read

Filtered nearest-neighbor search is nearest-neighbor search combined with an additional, non-vector condition that results must also satisfy — finding the closest vectors to a query, but only among those that also match some separate criterion, such as belonging to a specific category, falling within a certain price range, or being owned by a particular user. It’s an extremely common real-world requirement, since almost no practical search application wants results ranked purely by vector similarity with no ability to narrow that search down by other attributes, and it turns out to be a genuinely harder problem for a graph-based index like HNSW than it might first appear.

The most naive way to combine filtering with nearest-neighbor search would be to run the vector search first, exactly as usual, and then discard any results that don’t satisfy the filter condition afterward — an approach generally called post-filtering, covered in more depth on its own glossary page. This sounds reasonable until the filter condition happens to be restrictive: if only a small fraction of the dataset actually matches the filter, a normal top-k vector search might return k results, all of which then get discarded because none of them happen to satisfy the filter, leaving far fewer final results than were actually requested, or none at all, even though plenty of filter-matching points might exist elsewhere in the dataset that a search unaware of the filter never had a reason to look for.

The opposite naive approach, generally called pre-filtering, first identifies every item in the dataset that satisfies the filter condition, and then runs nearest-neighbor search only against that reduced subset. This avoids the problem of discarding too many results after the fact, but it introduces a different cost: identifying the full filter-matching subset ahead of time, and then somehow searching efficiently within just that subset, can be expensive or awkward depending on how the underlying index is structured, especially since a graph-based structure like HNSW‘s isn’t naturally built to be searched over an arbitrary, query-specific subset of its nodes — the graph’s connectivity was built assuming the full dataset is fair game, and restricting a search to only a scattered fraction of that graph can break the very connectivity assumptions that make greedy traversal work well in the first place.

What makes graph-based structures like HNSW specifically tricky to filter well?

HNSW’s search efficiency depends heavily on the graph’s connectivity — a greedy traversal needs to be able to move from node to node along edges that actually exist, trusting that following those edges tends to lead steadily toward the query. If a filter condition is applied by simply refusing to consider non-matching nodes as final results, the traversal itself can still wander freely through non-matching nodes along the way, using them as stepping stones even though they’ll never be returned, which mostly works but wastes computation on nodes that were never going to be candidates in the first place. If instead the filter is applied more aggressively by removing non-matching nodes from consideration entirely during traversal, the graph’s connectivity can effectively fragment for that specific query — a region of the graph that relied on a few non-matching “bridge” nodes to stay connected to the rest of the graph can become unreachable once those bridge nodes are excluded, even though the underlying full graph was perfectly well-connected before the filter was applied.

This connects directly to the bridge-edge and missing-bridge-in-connectivity concepts covered elsewhere in this documentation: a filter condition can effectively create new, query-specific bridge dependencies that the original graph construction had no way to anticipate, since the construction process had no idea in advance which arbitrary combination of filter values a future query might request. This is precisely why filtered search is considered a genuinely harder problem for graph-based ANN methods than for some other index structures, and why it remains an active area of both research and practical engineering effort.

How do real HNSW-based systems actually handle this problem in practice?

Production systems generally use some combination of the two naive strategies described above, refined with additional engineering: applying filtering during traversal but with logic that still allows the search to pass through non-matching nodes as stepping stones rather than removing them from the graph entirely, oversampling by retrieving more candidates than ultimately needed to compensate for some being filtered out afterward, or maintaining separate, filter-aware auxiliary structures that help route around the exact connectivity fragmentation problem described above. The right approach depends heavily on how selective the filter tends to be and how predictable the filter patterns are across the actual query workload, which is exactly the kind of practical trade-off explored in more depth in the filtered-and-hybrid-search glossary category and the corresponding chapter of this documentation.

Having covered why filtered search is a genuinely harder problem than it first appears for a graph-based structure like HNSW, the pre-filtering and post-filtering glossary pages are the natural next stop, since they go deeper into the two basic strategies introduced here and their respective trade-offs. From there, the filter-selectivity and filter-aware-graph-traversal glossary pages, under filtered and hybrid search concepts, look at the more sophisticated techniques real systems use to handle this problem well rather than relying on either naive approach alone.