Zettel — HNSW Single-Pass Pre-Filtering and Adaptive Fallback in searchlib

When a Vespa query combines a structured filter with nearestNeighbor(field, query_vector) (vespa/searchlib/src/vespa/searchlib/tensor/), proton evaluates the filter predicate first into a GlobalFilter (BitVector over the ready sub-database LID space) and passes that bitvector into the HNSW search blueprint before graph traversal begins.

Mechanism & Upstream Grounding

1. BitVector-Gated Greedy Traversal (vespa/searchlib/src/vespa/searchlib/tensor/hnsw_index.cpp):
   • During greedy layer descent and bottom-layer beam exploration (efSearch / targetHits), candidate neighbor LIDs arestill visited as graph stepping stones so connectivity is preserved, but only LIDs where global_filter.check(lid) == true are admitted into the top-K result heap.
2. Exact Brute-Force Fallback When Filter Selectivity Is Low:
   • NearestNeighborBlueprint (vespa/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.cpp) inspects the estimated filter hit ratio (estimated_filter_percent).
   • If the filter matches fewer documents than approximate-threshold (default 0.05 / 5% of the corpus), traversing the HNSW graph wastes distance computations on rejected nodes; Vespa automatically switches to an exact linear scan over only the LIDs set in the GlobalFilter bitvector.
3. Post-Filter / Filter-First Heuristics:
   • If the filter hit ratio exceeds filter-first-upper-limit, Vespa can use a filter-first exploration strategy that prioritizes edges whose target LIDs satisfy the filter.

Boundary Conditions & Trade-offs

• Eliminates the classic “post-filtering recall cliff” (where top-K ANN hits are computed globally and then intersected with a restrictive filter, yielding $0$ hits) while bounding worst-case latency when filter selectivity drops below 5% (see ai-rag and proton-lid-space-and-attribute-vectors).