Fiber-Navigable Search: A Geometric Approach to Filtered ANN
This work addresses filtered search for users needing efficient retrieval with metadata constraints, representing an incremental improvement over existing methods.
The paper tackles the problem of filtered approximate nearest neighbor search by introducing a geometric framework that uses local signals to guide a two-phase search algorithm, which outperforms FAISS HNSW on filtered search and classifies failures into three regimes that shift predictably with filter selectivity.
We present a geometric framework for filtered approximate nearest neighbor (ANN) search. Filtering a proximity graph by a metadata predicate produces a subgraph, a fiber, whose connectivity and geometry can differ sharply from the full graph. Using local signals, we propose a two-phase search algorithm that combines full-graph exploration with filtered-neighbor descent when the local geometry is favorable. These signals also classify search failures into three regimes: topological cuts, geometric folds, and genuine basins. A key observation is that all three share a common resolution: restarting the search in a fiber-present cluster near the query. To support this, we introduce a lightweight anchor structure that identifies such regions and restarts the search accordingly. We show empirically that the method outperforms FAISS HNSW on filtered search and the three failure regimes separate cleanly and shift predictably with filter selectivity.