Faster single-query binary search in FAISS

FAISS's exact binary search (IndexBinaryFlat) parallelizes only over queries, so a single query runs on one thread, and adding threads makes it slower. This repo contains a patch that splits the database across threads when there are few queries (mirroring what FAISS already does for float vectors), plus tests and reproducible benchmarks.

• Issue: facebookresearch/faiss#5700
• Pull request: facebookresearch/faiss#5701
• Related bug found along the way (float path, #5000): facebookresearch/faiss#5702

Result (Kaggle 4 vCPU, 1M x 1024-bit codes, k=10, same-build A/B): single query 3.03x faster (heap path) and 3.20x (counting path); 2 queries 1.5-2.0x; no regression for 4-64 queries; identical results (counting path: identical ids too). Real embeddings (100k all-MiniLM-L6-v2 binary codes, 384 bits): single query 2.02x. Tests: 53/53 Python binary tests and the C++ BinaryFlat.* tests pass.

Correctness fix found in review: the first version returned wrong results when search was called from inside an OpenMP parallel region; the follow-up commit fixes it and adds a C++ test. The same pattern affects FAISS's float database-parallel path (reported in #5702).

Files

• hamming_db_parallel_formatted.patch — full change (both commits), clang-format 21 clean, against the base commit in BASE_COMMIT
• followup_nested_parallel.patch — the follow-up fix on its own
• faiss_audit_v4.py — builds FAISS twice (PR before/after the fix), reproduces the nested-parallel bug, runs C++ + Python tests and the benchmark (Kaggle, CPU)
• faiss_build_and_test_v3.py — earlier build/test/benchmark script (includes the real-embedding check)
• faiss_thread_check.py — 5-minute check of the original problem on the stock faiss-cpu wheel

Method: problem found by reading the source, confirmed with a pre-registered benchmark rule before writing the fix. Built with help from an AI assistant (Claude); results reproducible with the scripts.