IndexHNSW ignores SearchParameters.sel when bounded_queue=False

[mmnhgo]

Summary

When searching an IndexHNSW index with SearchParameters.sel, the ID selector works correctly when bounded_queue=True.

However, when bounded_queue=False, the selector is ignored and the search may return IDs that are explicitly excluded.

This violates the contract of SearchParameters.sel: when it is non-null, only IDs accepted by the selector should be returned.

Bug type

Incorrect result

Environment

FAISS version: 1.14.2
Python: 3.x
OS: Windows
Installation: pip faiss-cpu
Index: IndexHNSWFlat
Metric: METRIC_L2

Minimal reproducer

import faiss
import numpy as np

xb = np.array(
    [
        [0.0, 0.0],
        [10.0, 0.0],
        [20.0, 0.0],
        [30.0, 0.0],
    ],
    dtype=np.float32,
)

xq = np.array([[0.0, 0.0]], dtype=np.float32)

index = faiss.IndexHNSWFlat(2, 4, faiss.METRIC_L2)
index.hnsw.efConstruction = 40
index.add(xb)

# Only ID 1 is allowed.
selector = faiss.IDSelectorRange(1, 2)

params = faiss.SearchParametersHNSW(
    efSearch=40,
    bounded_queue=False,
    sel=selector,
)

D, I = index.search(xq, 1, params=params)

print("labels:", I.tolist())
print("distances:", D.tolist())

assert I.tolist() == [[1]]
assert D.tolist() == [[100.0]]

Expected behavior

Because the selector only allows ID 1, the result should be:

labels: [[1]]
distances: [[100.0]]

Every returned label must satisfy:

sel->is_member(label)

This requirement should not depend on the value of bounded_queue.

Actual behavior

With bounded_queue=False, the result is:

labels: [[0]]
distances: [[0.0]]

ID 0 is not accepted by the selector, but it is still returned.

Comparison

Using the same index, data, query, and selector, but changing the parameter to:

bounded_queue=True

returns the correct result:

labels: [[1]]
distances: [[100.0]]

Why this is a bug

This is not normal approximate-nearest-neighbor recall behavior.

Even if HNSW fails to find the best allowed candidate, it must not return an ID that is explicitly rejected by the selector. The selector is a hard validity constraint on returned results, not a ranking preference.

In this example:

• ID 0 is explicitly excluded;
• ID 1 is the only allowed ID;
• filtering works when bounded_queue=True;
• filtering is ignored when bounded_queue=False.

This indicates a queue-path-specific ID filtering bug.

Impact

Applications that rely on SearchParameters.sel for permission filtering, tenant isolation, metadata filtering, or deleted-record filtering may receive IDs that should not be returned when bounded_queue=False.

This can cause filtering rules to be bypassed and restricted or cross-tenant data to appear in search results.

[lgong2025]

I did a deep dive into the C++ implementation to trace how SearchParameters are passed from Python to C++, and I found the root cause.

Root Cause

When bounded_queue=False, HNSW::search delegates to search_impl, which then calls search_from_candidate_unbounded_fixVT.

However, search_from_candidate_unbounded_fixVT does not accept params (or IDSelector) in its signature at all, so the SearchParameters object is completely dropped on this code path. As a result, candidates are evaluated and added to top_candidates without running the !sel || sel->is_member(id) check.

Code Pointers

1. Parameter Drop: In faiss/impl/HNSW.cpp (inside search_impl when bounded_queue == false):

   auto call = [&]<typename VTType>(VTType& vt_concrete) {
       return search_from_candidate_unbounded_fixVT<VTType, C>(
               hnsw,
               HNSW::Node(d_nearest, nearest),
               qdis,
               ef,
               vt_concrete,
               stats); // <-- `params` is missing from the function call here
   };

[YingzuoLiu]

Thanks for the analysis — this matches what I found when reproducing the issue on the current main branch.

I’ve opened draft PR #5508 with a focused fix. The unbounded path now keeps a separate result heap containing only selector-accepted IDs, while rejected nodes remain available for graph traversal. This prevents rejected IDs from being returned without allowing closer filtered nodes to displace valid results.

The regression test covers L2 and inner product, efSearch values of 1 and 40, and an empty selector.