Filtered Approximate Nearest Neighbor Search

This direction is split into other directions: metadata-constrained retrieval. Its last version stays readable and citable here.

Version 1 of 125 papers34 conceptsfrozen 2026-10-04

Modern information retrieval has moved beyond simple keyword matching to vector search, where items are represented as high-dimensional embeddings. However, real-world applications rarely ask for pure similarity. A user doesn't just want a "similar dress"; they want a "similar dress" that is in stock, under $50, and available in blue.

This intersection of semantic similarity and hard boolean constraints is the domain of Filtered Approximate Nearest Neighbor Search (FANNS). As noted by Harsha Vardhan Simhadri and colleagues in their analysis of the NeurIPS 2021 and 2023 Big ANN challenges, standard vector indices like HNSW or IVF often break when forced to respect these metadata constraints.

The Failure of Post-Filtering and Pre-Filtering

To understand why FANNS is difficult, consider the two naive approaches:

  1. Post-filtering: You search for the 100 nearest neighbors in the entire vector space and then discard those that don't match your metadata (e.g., "not in stock"). If your filter is highly selective—say, only 0.1% of items are in stock—you might end up with zero results, even if valid items exist further out in the vector space.
  2. Pre-filtering: You first find all items that match the metadata and then perform an exhaustive search among them. While accurate, this is essentially a linear scan, which defeats the purpose of using an approximate index for speed.

The core challenge, as described by Mengzhao Wang in the NHQ framework, is that the "semantic neighborhood" of a vector often has very little overlap with the "metadata subset" defined by a user's filters.

Hybrid Indexing and Graph Traversal

The most successful research direction involves Native Hybrid Querying, where the filtering logic is baked directly into the index traversal.

In graph-based indices like DiskANN (developed by Ravishankar Krishnaswamy and others), the search algorithm navigates a graph of vectors. In a filtered scenario, the algorithm must "hop" only to nodes that satisfy the boolean constraint. If the graph is not "filter-aware," the search can get stuck in a region where no neighbors satisfy the filter, leading to a "disconnection" in the search path.

To solve this, researchers have proposed several mechanisms:

  • Vamana Graphs: DiskANN uses a relaxed pruning strategy to ensure the graph remains navigable even when large portions of it are "turned off" by a filter.
  • Composite Indices: The NHQ framework achieves up to a 315x speedup by fusing vector similarity and attribute filtering into a single high-performance structure, avoiding the trade-offs of the "search then filter" paradigm.
  • Tree-Pruning: Mark Hamilton and the MosAIc team utilized inverted indices and tree-pruning to find artistic connections across cultures, allowing users to find a "Chinese version" of a "French dress" in real-time.

Beyond Categories: Windows and Patterns

While categorical filters (e.g., "Color: Blue") are the most common, recent work has expanded into more complex constraints:

  • Window Search: Joshua Engels and Julian Shun introduced the $\beta$-Window Search Tree to handle numeric range constraints, such as timestamps or price brackets, achieving significant speedups over traditional vector databases.
  • Pattern Constraints: Haoxuan Xie and Siqiang Luo developed VectorMaton, which combines suffix automata with HNSW graphs to allow similarity search constrained by specific text patterns or substrings.

The Path Forward

As Kai Zhang notes in a 2025 survey, the difficulty of these searches is often dictated by the "distribution factor"—how the filtered data points are physically distributed within the high-dimensional vector space. The goal of modern FANNS research is to create indices that are robust to these distributions, ensuring that whether a filter is broad or extremely rare, the system can find the most relevant results without an exhaustive scan.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_filtered_approximate_nearest_neighbor_se_6260b3d0,
  title = {Filtered Approximate Nearest Neighbor Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/filtered-approximate-nearest-neighbor-search/rdr_6260b3d0342049d6bf3e0c484d5d0d3b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_filtered_approximate_nearest_neighbor_se_6260b3d0_v1,
  title = {Filtered Approximate Nearest Neighbor Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/filtered-approximate-nearest-neighbor-search/rdr_6260b3d0342049d6bf3e0c484d5d0d3b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}