[Bug] HNSW top-k search skips brute-force fallback with an empty bitset

[zhuwenxing]

Summary

HNSW top-k search can return fewer than k results with an empty filter bitset even when sufficient indexed vectors are available and disable_fallback_brute_force=false.

The insufficient-results fallback in BaseFaissRegularIndexHNSWNode::Search uses bitset.size() - bitset.count() as the available-vector count. For a default-constructed bitset, that expression is zero, although an empty bitset means no filtering. The fallback is therefore never invoked.

Reproduced with HNSW_PQ through Milvus. Adding an all-pass scalar filter to the same query and index restores the missing results; explicitly disabling fallback then reproduces the shortage again.

Environment

• Knowhere: 2868882b02fd31fb658e276b20ad4309446e8173.
• Milvus server: 1759fb0961d, verified using get_server_version(detail=True); standalone, Linux/amd64, Cardinal-enabled build. Server logs confirm that the affected index is actually built and loaded as Knowhere HNSW_PQ.
• PyMilvus: 3.1.0rc83; Python 3.12; NumPy 2.5.3.
• autoIndex.enable=false; vector index version 11; scalar index version 5; storage version 3.
• 3000 indexed float32 vectors, dimension 128, COSINE, no deletes or nullable vectors.
• Build parameters: M=2, efConstruction=1, m=1, nbits=1, refine=true, refine_type=SQ8.
• The faulty condition is also present in current main at 67fe228222cdad2eaf0cb0c9cf67c18620b24db3 (source inspection only; runtime results below are from the affected version above).

Observed behavior

The original Milvus test, TestHnswPQBuildParams::test_hnsw_pq_build_params[params63], searches with nq=2, k=10, ef=64, refine_k=1 and no filter. Repeating the unchanged test 10 times on the affected server produced 1 failure and 9 passes. The failure returned 8 results instead of 10. The original Jenkins build 35 returned 7 and 8 results across the initial attempt and retry.

To compare fallback behavior without rebuilding the graph between requests, a separate experiment used 100 queries on one fixed 3000-vector index. Every inserted primary key satisfies id >= 0.

k	Filter	disable_fallback_brute_force	Results per query
50	empty	false	21 / 25 / 28 / 35; all 100 queries short
50	empty	true	Same counts
50	id >= 0	false	50 for all 100 queries
50	id >= 0	true	Same short counts as the unfiltered query
100	empty	false	21 / 25 / 28 / 35
100	id >= 0	false	100 for all 100 queries
500	empty	false	21 / 25 / 28 / 35
500	id >= 0	false	500 for all 100 queries

The short-result distribution was {21: 8, 25: 45, 28: 7, 35: 40}. Index metadata reported state=Finished, total_rows=3000, indexed_rows=3000, pending_index_rows=0.

With the all-pass filter and fallback enabled, the server logged:

[2026/09/10 06:21:20.618 +00:00] [WARN] [hnsw/faiss_hnsw.cc:1474]
required topk: 50, but the actual num of results got from hnsw: 25,
trigger brute force search as fallback for hnsw search

Graph construction and the candidate shortage vary between runs. The k=50/100/500 experiment is a separate controlled reproduction of the fallback defect, not a claim that the original k=10 test fails deterministically.

Reproduction

Use the affected server with autoIndex.enable=false and ensure that the actual backend is HNSW_PQ. In deployments that force AutoIndex, describe_index() may show the requested index type while the backend uses a different index; check the server build/load logs as well.

The script below uses the same seed, data generation, build parameters, and request matrix as the controlled experiment. It requires numpy and pymilvus. Set MILVUS_TOKEN to the authentication token for your test instance, then run:

python repro.py --uri http://localhost:19530

"""Temporary SDK diagnostic: compare HNSW/PQ search and build controls."""

import argparse
import json
import os
import uuid
from collections import Counter

import numpy as np
from pymilvus import DataType, MilvusClient

parser = argparse.ArgumentParser()
parser.add_argument("--uri", required=True)
parser.add_argument("--matrix", action="store_true")
parser.add_argument("--seed", type=int, default=35)
args = parser.parse_args()
client = MilvusClient(uri=args.uri, token=os.environ["MILVUS_TOKEN"], timeout=120)
print(json.dumps({"server": client.get_server_version(detail=True)}), flush=True)
rng = np.random.default_rng(args.seed)
xb = rng.uniform(-1, 1, (3000, 128)).astype("float32")
xq = rng.uniform(-1, 1, (100, 128)).astype("float32")
xb /= np.linalg.norm(xb, axis=1, keepdims=True)
xq /= np.linalg.norm(xq, axis=1, keepdims=True)
variants = [("baseline", {})]
if args.matrix:
    variants += [("M16", {"M": 16}), ("efConstruction200", {"efConstruction": 200})]
for label, change in variants:
    name = "diag_hnsw_pq_35_" + uuid.uuid4().hex[:12]
    try:
        schema = client.create_schema(auto_id=False)
        schema.add_field("id", DataType.INT64, is_primary=True)
        schema.add_field("vector", DataType.FLOAT_VECTOR, dim=128)
        client.create_collection(name, schema=schema, consistency_level="Strong")
        client.insert(name, [{"id": i, "vector": v.tolist()} for i, v in enumerate(xb)])
        client.flush(name)
        index_params = client.prepare_index_params()
        build = {"M": 2, "efConstruction": 1, "m": 1, "nbits": 1,
                 "refine": True, "refine_type": "SQ8", **change}
        index_params.add_index("vector", index_type="HNSW_PQ", metric_type="COSINE", params=build)
        client.create_index(name, index_params)
        print(json.dumps({"variant": label, "index": client.describe_index(name, "vector"),
                          "stats": client.get_collection_stats(name)}), flush=True)
        client.load_collection(name)
        for topk in [10, 20, 50, 100, 500]:
            for expr in ["", "id >= 0"]:
                for disable in [False, True]:
                    search = {"ef": max(64, topk), "refine_k": 1, "disable_fallback_brute_force": disable}
                    results = client.search(name, data=xq.tolist(), search_params=search, filter=expr, limit=topk)
                    print(json.dumps({"collection": name, "topk": topk, "expr": expr,
                                      "disable_fallback": disable,
                                      "counts": dict(Counter(len(hits) for hits in results))}), flush=True)
    finally:
        if client.has_collection(name):
            client.drop_collection(name)
client.close()

Expected behavior

With fallback enabled, an empty bitset should permit the same insufficient-results fallback as an explicit all-pass bitset. On this dataset, where 3000 eligible vectors are available, the search should return the requested number of results for the tested values of k.

Root cause and suggested fix

The affected fallback condition is:

if (std::cmp_less(real_topk, k) && real_topk < bitset.size() - bitset.count() &&
    bf_index_wrapper_ptr != nullptr && !hnsw_cfg.disable_fallback_brute_force.value()) {
    // Trigger brute-force fallback.
}

For a default-constructed BitsetView, both size() and count() are zero. The second predicate is false for every real_topk. Milvus's sealed-segment unfiltered fast path passes such an empty bitset when all rows are visible.

The available-vector calculation should distinguish an absent bitmap from an actual filter bitmap. For the absent-bitmap case, use the count of the index being searched; for actual filters, preserve the correct filtered count and ID domain. Visible-prefix bounds, nullable mappings, and sub-index mappings must remain respected.

Suggested regression coverage: default empty bitset, explicit all-pass bitset, partially filtered bitset, fewer than k eligible vectors, and explicitly disabled fallback. A disconnected or otherwise candidate-limited test graph would avoid relying on probabilistic graph construction.

Related issues checked

• milvus-io/milvus issue 48762 reports the same extreme-parameter result shortage for HNSW_SQ. A maintainer explicitly noted that the HNSW_PQ and HNSW_PRQ minimum-boundary cases can also exhibit it. The issue was closed after PR 48788 relaxed only the HNSW_SQ testcase to require nonempty results. That test-only change did not address the fallback predicate reported here. This report distinguishes expected graph candidate limitations from the configured fallback being skipped for an absent bitmap.
• milvus-io/milvus issue 51821 is open and reports poor HNSW recall on unnormalized IP data. A maintainer comment also notes that insufficient-result fallback did not activate for an unfiltered search. That is a related symptom; the present reproduction uses normalized COSINE vectors and isolates the empty-bitset fallback condition with an all-pass filter comparison.

Issue 1561 and its fix, PR 1562, address the selector inside IndexBruteForceWrapper::range_search. This report concerns the decision to invoke fallback in ordinary top-k Search, before the brute-force wrapper runs.

The affected Knowhere commit already contains PR 1562's merge commit c21d72aa6ac1ca05b6357a2250f0e21374a04581, verified with git merge-base --is-ancestor. This is a separate defect, not a report of that range-search fix being absent.