Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5078
Four fixes in `faiss/utils/sorting.cpp`:
**1. OpenMP directive fix in `fvec_argsort_parallel`**
The initialization loop used `#pragma omp parallel` without the `for` directive. This caused every thread to execute the entire loop independently rather than distributing iterations. With `nt` threads, each `permA[i]` was written by all `nt` threads concurrently — a data race under the C++ memory model (multiple unsynchronized writes to the same non-atomic location), and O(n * nt) wasted work instead of O(n). Fixed by changing to `#pragma omp parallel for`.
In practice, all threads write the same value (`permA[i] = i`), so the output was always correct despite the UB. The fix eliminates the undefined behavior and the redundant work.
**2. RAII memory management in `fvec_argsort_parallel`**
Replaced `new size_t[n]` / `delete[] perm2` with `std::vector<size_t>`. The old code had no realistic exception path between allocation and deallocation (all intermediate code is either C functions or non-throwing OpenMP regions), but the manual `new`/`delete` pattern is fragile against future edits that might introduce a throwing path. The `std::vector` provides RAII lifetime management with no behavioral change.
**3. Removed debug `printf` in `fvec_argsort_parallel`**
A leftover `printf("merge %d %d, %d threads\n", ...)` in the parallel merge loop wrote to stdout during normal operation. Removed.
**4. Missing early termination in `hashtable_int64_to_int64_lookup`**
The linear probing loop did not check for empty slots (`tab[slot * 2] == -1`). In an open-addressing hash table with no deletion support, an empty slot is definitive proof that the key was not inserted — the insert function would have placed it there or earlier. Without this check, lookups for absent keys probed every slot in the bucket before the wrap-around termination at `slot == hk_i`. The fix adds the standard empty-slot check, matching the structure of the insert function (`hashtable_int64_to_int64_add`). This is a performance optimization — the old code always returned the correct result (`-1` after a full bucket scan), just slower.
Reviewed By: mnorris11
Differential Revision: D100317917
fbshipit-source-id: aadfe33b1d76c34e04db7fe0c9b7ca53b4a30c71
Summary:
Extend the POSIX mmap reader to Apple platforms and use MAP_FAILED for mmap error checks while keeping madvise best-effort.
Update the C++ and Python mmap tests to exercise Darwin, and stop linking faiss_test against the Python example extension so Python-enabled test builds can run on macOS.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5058
Reviewed By: junjieqi
Differential Revision: D100351635
Pulled By: alibeklfc
fbshipit-source-id: f384251a634c7d3154103dbc763293b52b093ee8
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5056
Add deserialization-time validation for FastScan `M2` across all six
FastScan index types to reject corrupted or malicious index files that
would cause heap buffer overflows during search.
During normal construction, `M2 = roundup(M, 2)` is an invariant
maintained by `init_fastscan()`. During deserialization, `M2` is read
directly from the file and was not validated. A corrupted file with
`M2 < M` causes `compute_quantized_LUT` to write `M * ksub` bytes
into a buffer sized for `M2 * ksub` bytes, producing an out-of-bounds
write. The `memset` that zeroes padding from M to M2 additionally
underflows as an unsigned subtraction when `M2 < M`.
1. **Added `validate_fastscan_fields()` helper**:
Consolidates all FastScan field validation into a single function:
M > 0, ksub > 0, bbs > 0 and 32-aligned, M2 == roundup(M, 2),
and overflow checks for ksub * M and ksub * M2.
2. **Non-IVF FastScan paths (already had partial validation)**:
Replaced inline checks in IndexPQFastScan, IndexAdditiveQuantizer-
FastScan, and IndexRaBitQFastScan with calls to the new helper,
adding the missing M2 consistency check.
3. **IVF FastScan paths (had no validation at all)**:
Added validation to IndexIVFPQFastScan, IndexIVFAdditiveQuantizer-
FastScan, and IndexIVFRaBitQFastScan, which previously had zero
checks on any FastScan fields.
Reviewed By: mnorris11
Differential Revision: D99738294
fbshipit-source-id: 8e334993b0e8b4375f9ec173c20754e301b7c9f6
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5055
Add deserialization-time validation for the `storage_kind` field in SVS
index types (IndexSVSVamana, IndexSVSVamanaLVQ, IndexSVSVamanaLeanVec)
to reject corrupted or malicious index files before they can cause
crashes.
1. **Read `storage_kind` as int and range-check before cast**:
`storage_kind` was previously read directly into the `SVSStorageKind`
enum via `READ1`, which is undefined behavior for out-of-range values.
Now read into a temporary `int`, validate the value is in
`[0, SVS_count)`, and only then cast to `SVSStorageKind`. This rejects
invalid values at deserialization time with a `FaissException` instead
of reaching `to_svs_storage_kind()` where the `default` branch calls
`FAISS_ASSERT(false)` and aborts the process.
2. **Add `SVS_count` sentinel to `SVSStorageKind` enum**:
Follows the convention used by `QT_count`, `ST_count`, and
`DMT_count` in other FAISS enums. The deserialization validation
uses this sentinel so it automatically stays correct when new
storage kinds are added.
Reviewed By: mnorris11
Differential Revision: D99722676
fbshipit-source-id: 557cf91a963d1d93171fea2a67ba99f19b9b3420
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5040
Add the missing `key < nlist` upper-bound check in
`IndexIVF::search1()`, which was the only IVF search entry point
lacking this validation. The other two paths —
`search_preassigned()` and `range_search_preassigned()` — already
had this check.
Also add deserialization acceptance tests verifying that IVF indexes
with various quantizer states deserialize correctly:
1. **Surplus centroids** (`ntotal > nlist`):
Produced by `shard_ivf_index_centroids()`, which distributes
all of the original quantizer's centroids across shards without
adjusting `nlist`. The search-time `key < nlist` bounds check
prevents OOB access if the quantizer returns out-of-range keys.
2. **Trained quantizer** (`ntotal == nlist`):
The normal trained IVF state.
3. **Sharded quantizer** (`0 < ntotal < nlist`):
Also produced by `shard_ivf_index_centroids()`, when the
original quantizer has `ntotal == nlist` and centroids are
split across shards.
4. **Untrained quantizer** (`ntotal == 0`):
Legitimate for custom inverted list management.
Reviewed By: mnorris11
Differential Revision: D99494237
fbshipit-source-id: 6a76b55f104b9c233dfdd2625bb0336ed8061463
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5072
Fix correctness bugs in `NNDescent` `Nhood` copy/move operations and `gen_random` bounds.
## Bug 1: Broken Nhood copy constructor and copy assignment operator
The copy constructor and copy assignment operator for `Nhood` were incomplete:
- Copy assignment used `std::back_inserter` to append to `nn_new` instead of replacing it, leading to duplicate entries on reassignment and heap-use-after-free on self-assignment.
- Neither operation copied `pool`, `nn_old`, `rnn_old`, or `rnn_new`, meaning copied `Nhood` objects had missing neighbor data.
- This caused data loss when `std::vector<Nhood>` reallocated during `push_back`.
Fixed both operations to properly copy all 6 data members. Added self-assignment guard (`if (this != &other)`) to the copy assignment operator. Changed the copy constructor to use a member initializer list in declaration order to avoid `-Wreorder` warnings.
**Proof:** `NhoodCopy.CopyConstructorPreservesAllFields` and `NhoodCopy.CopyAssignmentPreservesAllFields` fail without the fix — `pool.size()` is 0 (expected 3), `nn_old`, `rnn_new`, `rnn_old` are all empty. `NhoodCopy.CopyAssignmentSelfAssign` triggers heap-use-after-free without the self-assignment guard. `NhoodCopy.VectorReallocationPreservesData` shows data loss during `std::vector<Nhood>` reallocation.
## Bug 2: Division by zero in `gen_random`
When `size == N`, the expression `rng() % (N - size)` is a division by zero (undefined behavior). This occurs in `search()` when `search_L` or `topk` equals `ntotal`, because `L_2 = max(search_L, topk)` is passed to `gen_random(rng, init_ids.data(), L_2, ntotal)`.
Added a precondition assertion (`size > 0 && size <= N`) and a Fisher-Yates shuffle for the `size == N` special case.
**Proof:** `TestNNDescentGenRandom.test_search_L_equals_ntotal` crashes (process killed by SIGFPE) without the fix, passes with it.
## Performance: Added move constructor and move assignment operator
Since `std::mutex` is neither copyable nor movable, the compiler cannot generate implicit move operations for `Nhood`. With user-defined copy operations, implicit move generation is suppressed entirely. Without explicit move operations, `std::vector<Nhood>::push_back(Nhood&&)` falls back to copy — 5 unnecessary vector allocations per element.
Added `noexcept` move constructor and move assignment operator. `noexcept` is required for `std::vector` to prefer move over copy during reallocation. The move assignment operator is included for Rule of Five consistency.
**Proof:** All tests pass both with and without move operations, confirming these are a performance optimization, not a correctness fix.
## Cleanup: Removed misleading `omp_get_thread_num()`
The RNG seed in `nndescent()` was `random_seed * 6577 + omp_get_thread_num()`. This function is not inside any `#pragma omp parallel` region — the call chain is `IndexNNDescent::add()` -> `NNDescent::build()` -> `NNDescent::nndescent()`, all sequential. Per the OpenMP specification, `omp_get_thread_num()` returns 0 in sequential context. The `+ 0` is dead code.
**Proof:** No behavioral change. The seed was always `random_seed * 6577`.
Reviewed By: mnorris11
Differential Revision: D100155792
fbshipit-source-id: 042a7d0a53a7696915a96bf1e48a464507f044b3
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5053
C++ exceptions thrown inside `#pragma omp parallel` regions that are not
caught within the region call `std::terminate` — they cannot propagate
across thread boundaries.
`IndexIVF::range_search_preassigned` had the same class of bugs fixed in
`search_preassigned` by D99455250:
1. **`scan_list_func` lambda**:
`FAISS_THROW_IF_NOT_FMT(key < nlist)` was above the try-catch block,
so a corrupt key >= nlist would throw uncaught and call
`std::terminate`.
2. **Outer parallel region**:
`get_InvertedListScanner()`, `scanner->set_query()`, and
`FAISS_THROW_IF_NOT(scanner.get())` had no try-catch at all.
Fixes:
1. Moved the existing try-catch in `scan_list_func` up to also cover the
key validation.
2. Wrapped the entire `#pragma omp parallel` body in a try-catch that
uses the existing `interrupt`/`exception_string`/`exception_mutex`
pattern to safely propagate exceptions out of the parallel region.
Reviewed By: mnorris11
Differential Revision: D99879998
fbshipit-source-id: e768372cbaf8a22a9459fc3fd9b9df6e019897a6
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5063
Fix two bugs in `fbcode/faiss/impl/NSG.cpp`:
**Bug 1: `init_ids[i]` → `init_ids[num_ids]` in `search_on_graph`**
The init loop in `search_on_graph` reads neighbors of the enterpoint from the
knn_graph. When an entry has `id >= ntotal`, it is skipped via `continue`. The
loop variable `i` advances but `num_ids` (the write pointer) does not. The old
code wrote `init_ids[i] = id`, placing valid entries at non-contiguous positions
and leaving gaps in between. The gap-filling loop that follows starts from
`num_ids`, so it never overwrites the internal gaps.
Example with neighbors `[5, 99999, 3, 99999, 7]` and `ntotal=100`:
| i | id | old: `init_ids[i]=id` | new: `init_ids[num_ids]=id` |
|---|-------|-----------------------|-----------------------------|
| 0 | 5 | `init_ids[0] = 5` | `init_ids[0] = 5` |
| 1 | 99999 | skip (gap at [1]) | skip |
| 2 | 3 | `init_ids[2] = 3` | `init_ids[1] = 3` |
| 3 | 99999 | skip (gap at [3]) | skip |
| 4 | 7 | `init_ids[4] = 7` | `init_ids[2] = 7` |
Old result: `[5, 0, 3, 0, 7, ...]` — gaps contain 0 (from `vector<int>`
zero-initialization). The consumption loop reads these zeros as node IDs,
biasing the search pool toward node 0 during graph construction and degrading
graph quality.
Fixed result: `[5, 3, 7, ...]` — valid entries packed contiguously, gap-filling
starts from the correct position.
**Bug 2: `sync_prune` out-of-bounds access**
`sync_prune` accesses `pool[start]` without bounds checking. Two cases cause
out-of-bounds reads:
- Pool is empty after augmentation
- Pool contains only the query node itself (e.g., `ntotal=1`)
In both cases `start` advances past `pool.size()` and `pool[start]` is an
out-of-bounds vector read — undefined behavior that crashes under ASAN and
silently corrupts the graph in release builds.
Trace for `ntotal=1, L=1`:
1. `search_on_graph` returns `pool = [{id:0, dist:0}]`
2. `sync_prune(q=0)`: `pool[0].id == q` → `start++` → `start=1 == pool.size()`
3. Old code: `result.push_back(pool[1])` — OOB read
4. Fix: guard checks `start >= pool.size()`, fills graph row with `EMPTY_ID`
**Other fixes:**
- Replace `min = 1e6` (float-to-int truncation) with `std::numeric_limits<int>::max()`
- Remove `srand(0x1998)` from the NSG constructor (global RNG side effect)
Reviewed By: mnorris11
Differential Revision: D100024850
fbshipit-source-id: 0d290801658e381e198b6c6ab54ebe981e0f09f3
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5069
Remove the 10 global bare-name using declarations (simd16uint16,
simd32uint8, simd8uint32, simd8float32, simd256bit, simd512bit,
simd32uint16, simd64uint8, simd16float32) from simdlib_dispatch.h.
These aliases resolved through SINGLE_SIMD_LEVEL which is NONE in DD
mode, creating a trap where per-ISA TU code accidentally uses scalar
emulation. Each file that needs the aliases now declares its own using
with an explicit SIMD level, making the dependency visible.
Behavior-preserving: all files use the same SINGLE_SIMD_LEVEL they
used before, but now explicitly.
Reviewed By: mdouze
Differential Revision: D100033901
fbshipit-source-id: 2db034c2868de275a5f018d886264762776548c5
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5061
Roll out the `for_all_simd_levels` decorator to 62 test classes across
11 test files. This ensures that every available SIMD level (NONE, AVX2,
AVX512, etc.) is exercised in CI, rather than only testing at the
auto-detected (highest) level.
Previously only `TestExtraDistances` in `test_extra_distances.py` used
the decorator. Now all test files covering DD-dispatched code paths are
parameterized: distances, PQ, SQ, fast scan, RaBitQ, partitioning,
HNSW, and binary indices.
Changes:
- Add `for_all_simd_levels` to 62 test classes across 11 test files
- BUCK: move decorated test targets to `supports_static_listing = False`
(required because the decorator replaces class names with None,
breaking TPX's static test enumeration)
- test_fast_scan.py, test_fast_scan_ivf.py: apply decorator manually
after dynamic `setattr` method generation for TestAQFastScan and
TestIVFAQFastScan (the `setattr` loops reference the class by name)
- test_rabitq_fastscan.py: extract `_create_fastscan_index` as
module-level helper to fix cross-class method reference that broke
when TestRaBitQFastScan was replaced by the decorator
- IndexFastScan.cpp: fix `search_implem_14` to auto-cap `qbs` based
on `bbs`. The accumulate loop dispatch table only instantiates
certain (nq, BB) pairs (e.g. BB=2 only has nq=1,2). Previously,
using bbs=64 with the default qbs (batch of 4) would crash with
"nq=3 bbs=64 not instantiated". Now the query batch size is
automatically capped to the max nq supported for the given BB.
Exposed by per-level testing of test_factory_with_batch_size.
Reviewed By: mdouze
Differential Revision: D99978401
fbshipit-source-id: 54858f3810bab91ac5ec8bf0ce0d55a77710727b
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5050
- Implement balanced assignment in clustering.py based on notebook N10159950
- add a test that shows we improve the imabalace at some cost in MSE
Reviewed By: algoriddle
Differential Revision: D99819394
fbshipit-source-id: 568b6deb7d2b95b8228dbb276c5578df23b01a96
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5025
In c++ when running in dev mode:
```
Crash chain:
1. index->add(1, vec) → IndexIVF::add_with_ids() (line 190)
2. quantizer->assign() → Index::assign() → IndexHNSW::search() — searches the HNSW coarse quantizer with the NaN
vector
3. HNSW::search() computes d_nearest = qdis(entry_point) — this returns NaN because the input vector has NaN
4. NaN is pushed into MinimaxHeap candidates. All comparisons with NaN return false, corrupting heap ordering
5. search_from_candidates() pops a garbage node ID v0 from the corrupted heap
6. neighbor_range(v0, ...) hits FAISS_CHECK_RANGE_DEBUG — v0 is out of bounds → crash
```
In python test or opt mode:
```
The test timed out — it hung instead of crashing. This is consistent with the analysis: in the Python bindings (which
run with mode/opt, so no debug assertions), pop_min returns -1, neighbor_range(-1, ...) doesn't crash on the
assertion (it's a debug-only check), and instead accesses offsets[-1] which is undefined behavior. The NaN corrupts
the heap, the search loops forever because nvalid never decrements when pop_min returns -1.
So in Python/opt mode: no stack trace, just a hang. The C++ debug build crashes with the assertion. Both are fixed by
the same push() NaN→+inf change in HNSW.cpp.
```
Performance impact??
--
it is in the tightest loop in search_from_candidates. Claude seems to think it is fine:
```
In search_from_candidates (line 707), push() is called for every neighbor visited during greedy graph traversal — batched 4 at a time via
add_to_heap. This is indeed the tightest inner loop in HNSW search.
What std::isnan actually costs
std::isnan(float) on x86_64 compiles to essentially v != v — a single ucomiss + conditional jump (jp). That's 1-2 instructions.
Context: what else happens per push call
Each push call is preceded by significantly more expensive work:
1. Distance computation (distances_batch_4 at line 718): ~2×d FLOPs per vector (e.g., ~256 FLOPs for d=128) NOTE: HNSW.cpp:718-726 (qdis.distances_batch_4(...))
2. Existing comparisons in push: k == n, v >= dis[0], potential heap_pop/heap_push which are O(log efSearch) with memory accesses NOTE: HNSW.cpp:1401 (k == n), 1402 (v >= dis[0]), 1408 (heap_pop), 1410 (heap_push)
3. Visited table check (vt.set) with prefetching NOTE: HNSW.cpp:689 (vt.prefetch(v1)) and 714 (vt.set(v1))
The isnan check is ~1 instruction compared to hundreds for the distance computation. Even against just the heap operations (several
comparisons + pointer chasing), it's a rounding error.
Branch prediction
Since NaN distances essentially never occur in normal operation, this branch is always not-taken. The branch predictor will learn this
within the first few iterations and predict it perfectly for the remainder of the search. A perfectly-predicted not-taken branch is ~0
cycles on modern CPUs.
```
And mini benchmark:
```
┌────────┬────────────────────────┬────────────────────────┬───────────────────┐
│ │ With NaN check (run 1) │ With NaN check (run 2) │ Without NaN check │
├────────┼────────────────────────┼────────────────────────┼───────────────────┤
│ Mean │ 401.146 ms │ 400.515 ms │ 401.191 ms │
├────────┼────────────────────────┼────────────────────────┼───────────────────┤
│ Median │ 396.746 ms │ 398.172 ms │ 398.520 ms │
├────────┼────────────────────────┼────────────────────────┼───────────────────┤
│ Min │ 389.939 ms │ 388.670 ms │ 391.850 ms │
├────────┼────────────────────────┼────────────────────────┼───────────────────┤
│ Stddev │ 18.903 ms │ 7.833 ms │ 8.164 ms │
└────────┴────────────────────────┴────────────────────────┴───────────────────┘
```
I wanted to make sure it worked regardless of metric type:
```
For inner product (and cosine, which is IP after normalization), HNSW wraps the distance computer in NegativeDistanceComputer, which
negates the result. This means all metrics flow through the MinimaxHeap with the same convention: smaller = better.
So the NaN → +inf replacement works correctly for all metrics:
┌────────┬──────────────────────────────┬──────┬───────┬─────────────────┐
│ Metric │ qdis() returns │ Best │ Worst │ +inf means │
├────────┼──────────────────────────────┼──────┼───────┼─────────────────┤
│ L2 │ ‖x-q‖² │ 0 │ +inf │ worst (correct) │
├────────┼──────────────────────────────┼──────┼───────┼─────────────────┤
│ IP │ -<x,q> (negated) │ -∞ │ +inf │ worst (correct) │
├────────┼──────────────────────────────┼──────┼───────┼─────────────────┤
│ Cosine │ -<x̂,q̂> (negated, normalized) │ -1 │ +inf │ worst (correct) │
└────────┴──────────────────────────────┴──────┴───────┴─────────────────┘
In all cases, +inf sits at the top of the CMax heap and gets evicted first when the heap is full (v >= dis[0] returns early at line 1402).
And pop_min() will never select it over any finite-distance candidate. The semantics are correct regardless of metric type.
```
Reviewed By: mdouze
Differential Revision: D99036639
fbshipit-source-id: e5d6392e800f243f66ce283c8cd35fe0e7558229
Summary:
- Fix duplicate word "the the" to "the" in `faiss/utils/quantize_lut.h` (comment) and `benchs/README.md`
- Fix duplicate word "to to" to "to" in `faiss/IndexBinaryHNSW.cpp` (comment)
- Fix subject-verb agreement "This produce" to "This produces" in `INSTALL.md`
- Fix broken grammar "it does not the case" to "it is not the case" in `tests/test_residual_quantizer.py`
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5044
Test Plan:
- [ ] No functional code changes; only comments, documentation, and test comments are modified
- [ ] Verified each fix is a clear typo/grammar correction
🤖 Generated with [Claude Code](https://claude.com/claude-code)
Reviewed By: mnorris11
Differential Revision: D99692631
Pulled By: alibeklfc
fbshipit-source-id: e3ae88ba4ca732e9f620e1c205f51e4b827d0730
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5037
C++ exceptions thrown inside `#pragma omp parallel` regions that are not
caught within the region call `std::terminate` — they cannot propagate
across thread boundaries.
`IndexIVF::search_preassigned` had multiple unguarded throw sites inside
its OpenMP parallel region:
1. **`scan_one_list` lambda**:
`FAISS_THROW_IF_NOT_FMT(key < nlist)` and `scanner->set_list()` were
above the try-catch block, so a corrupt key >= nlist would throw
uncaught and call `std::terminate`.
2. **Outer parallel region**:
`get_InvertedListScanner()` and `scanner->set_query()` had no
try-catch at all.
Fixes:
1. Moved the existing try-catch in `scan_one_list` up to also cover the
key validation and `set_list` calls.
2. Wrapped the entire `#pragma omp parallel` body in a try-catch that
uses the existing `interrupt`/`exception_string`/`exception_mutex`
pattern to safely propagate exceptions out of the parallel region.
Reviewed By: mnorris11
Differential Revision: D99455250
fbshipit-source-id: 41e8816d71c031b1e8526f76bd5a8936f4d4f160
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5022
I used the C++ benchmark in https://github.com/facebookresearch/faiss/pull/4971 but modified it a lot to measure on my machine.
```
The BLAS threshold for flat distance computation was a fixed query count (nq < 20), regardless of vector dimension. This meant BLAS was
used for as few as 20 queries even at d=128, where the sequential SIMD path is 10-25x faster.
The optimal crossover between sequential and BLAS depends on the total work in the query matrix (nq × d), not just query count.
Benchmarking across dimensions shows the crossover at roughly nq × d ≈ 128,000:
┌──────┬────────────────────┬──────────────────────────────┐
│ d │ Old threshold (nq) │ New effective threshold (nq) │
├──────┼────────────────────┼──────────────────────────────┤
│ 128 │ 20 │ 1000 │
├──────┼────────────────────┼──────────────────────────────┤
│ 256 │ 20 │ 500 │
├──────┼────────────────────┼──────────────────────────────┤
│ 512 │ 20 │ 250 │
├──────┼────────────────────┼──────────────────────────────┤
│ 1024 │ 20 │ 125 │
├──────┼────────────────────┼──────────────────────────────┤
│ 2048 │ 20 │ 63 │
└──────┴────────────────────┴──────────────────────────────┘
This change replaces the comparison nq < threshold with nq * d < threshold and sets the default to 128,000.
Speedup vs old default (nb=100,000, L2 (same as IP for me), compiled with optimizations):
nq | d=128 | d=256 | d=512 | d=1024 | d=2048
----|-------|-------|-------|--------|-------
20 | 22.8x | 9.3x | 4.5x | 2.6x | 1.4x
50 | 19.4x | 9.3x | 4.7x | 2.0x | 1.2x
100 | 13.3x | 5.6x | 2.1x | 1.0x | 1.0x
200 | 8.2x | 2.7x | 1.1x | 1.0x | 1.0x
500 | 3.2x | 1.0x | 1.0x | 1.0x | 1.0x
1000 | 1.0x | 1.0x | 1.0x | 1.0x | 1.0x
No regressions observed — the worst case is d=1024, nq=100 at 0.99x (within noise).
```
Reviewed By: mdouze
Differential Revision: D99032435
fbshipit-source-id: 45153e1d5add3ab20efa0e1e90cfc18533f4ac97
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5033
Add test coverage for `validate_HNSW()` checks in `index_read.cpp` that
were previously untested. These validations were introduced in D92907607
(Feb 2026) but had no dedicated unit tests.
Five new tests in `test_read_index_deserialize.cpp`:
1. **`HNSWNeighborNegativeId`**:
Neighbor ID of -5 (not the -1 sentinel) is rejected during deserialization.
2. **`HNSWNeighborIdTooLarge`**:
Neighbor ID >= ntotal is rejected during deserialization.
3. **`HNSWEntryPointOutOfRange`**:
Entry point >= ntotal is rejected during deserialization.
4. **`HNSWValidNeighborsSearchWorks`**:
A hand-crafted HNSW with valid neighbor data deserializes and searches
correctly, confirming the happy path through `validate_HNSW()`.
5. **`BinaryHNSWNeighborNegativeId`**:
Same as (1) for the binary HNSW index path (`IBHf` fourcc).
A `push_hnsw_with_neighbors()` helper is added to construct serialized
HNSW graphs with explicit neighbor data for use by these and future tests.
Reviewed By: mnorris11
Differential Revision: D99334840
fbshipit-source-id: 6bb38eb78ea20f7215eb0046de7398d07f14ac35
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5032
Convert supported metric type assert to throw in `to_svs_metric()` to
better support tests that expect exceptions when processing invalid input.
There are two vectors that reach `to_svs_metric()` with an unsupported
metric:
1. **Deserialization** (`deserialize_impl()`):
A invalid binary index with fourcc `"IBFf"`
(IndexBinaryFromFloat) wrapping an SVS float index (`"ISVF"`,
`"ILVQ"`, etc.) can carry any valid `MetricType` in the
serialized stream. When the metric is not L2 or INNER_PRODUCT,
`to_svs_metric()` is called with the unsupported value during
`deserialize_impl()`.
2. **Programmatic construction** (`create_impl()`):
Creating an SVS index (e.g., `IndexSVSFlat`) with an unsupported
metric and calling `add()` triggers `create_impl()` which calls
`to_svs_metric()`. This is a user-error path.
Reviewed By: mnorris11
Differential Revision: D99336458
fbshipit-source-id: ee5449b72e957a5e7eb77f651471f84c34e5c122
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5029
1. **Null pointer dereference in `deserialize_impl`**:
`IndexSVSVamana::deserialize_impl()` and `IndexSVSFlat::deserialize_impl()`
called `impl->load(...)` as a member function on a null `impl` pointer,
causing a SIGSEGV. The `load` function is actually a static factory method
(like `build` and `destroy`), so it should be called as
`ClassName::load(&impl, ...)` instead. This matches the pattern used in
`IndexSVSVamanaLeanVec::deserialize_training_data()` which correctly calls
`svs_runtime::LeanVecTrainingData::load(&tdata, in)`.
2. **Added post-load validation**:
Added `FAISS_THROW_IF_NOT_MSG(impl, ...)` after `load()` returns to ensure
the impl pointer was actually populated.
3. **Added tests**:
Added deserialization tests that provide invalid SVS stream data and verify
the load fails with a FaissException rather than crashing.
Reviewed By: mnorris11
Differential Revision: D99117347
fbshipit-source-id: 3165048d06dc5ab66fcf83ecba3a144605c5732f
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5028
The ZnSphereCodecRec constructor builds a decode cache by calling
decode() for every lattice point at the cache level. The number of
lattice points grows as O(r2^(dim/2)), so moderate r2 values with
higher dimensions cause excessive CPU usage.
The existing nv_cum memory cap (2^27 uint64_t entries) does not catch
this because nv_cum grows as O(r2^2) -- the decode cache is the
binding constraint for these inputs.
**Fix: Add decode cache size check in ZnSphereCodecRec constructor**:
Track cumulative decode cache entries within the existing decode
cache loop. Cap at 2^27 total floats (~512 MB), aligned with
the nv_cum memory cap which also uses 2^27 entries. This bounds
both memory and computation for all callers, not just
deserialization.
Reviewed By: mnorris11
Differential Revision: D99166802
fbshipit-source-id: 442ba2f5ea6b46309e3598b97953cf4c38fa443a
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5024
Fixes a null-deref crash in `IndexIDMap2::construct_rev_map()` when
deserializing a crafted index where `id_map.size() != ntotal`.
1. **Validation in index_read.cpp**:
Added a `FAISS_THROW_IF_NOT_FMT` check after reading the `id_map`
vector in the `IxMp`/`IxM2` deserialization path, verifying that
`id_map.size() == ntotal` before `construct_rev_map()` is called.
The binary index path (`IBMp`/`IBM2`) already had this check.
2. **Test in test_read_index_deserialize.cpp**:
Added `IndexIDMap2IdMapSizeMismatch` test that constructs a serialized
`IndexIDMap2` with `ntotal=2` but `id_map` containing 5 entries, and
verifies deserialization throws with the expected error message.
Reviewed By: mnorris11
Differential Revision: D99138339
fbshipit-source-id: cfcc5a4daf83bb6fbda324d15f946340eee259c0
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5023
Add deserialization-time validation to catch AdditiveQuantizer dimension
mismatches that would cause crashes during search operations.
1. **AQ dimension vs index dimension cross-check**:
Added `validate_aq_dimension_match()` helper that verifies `aq.d == idx.d`
for all AdditiveQuantizer-based index types. Without this check, a
corrupted index where AQ.d != Index.d causes `compute_LUT()` to read
codebooks out of bounds (query vectors are sized for Index.d while
codebooks are laid out for AQ.d).
2. **Coverage across all AQ index types**:
- IndexResidualQuantizer (IxRq/IxRQ)
- IndexLocalSearchQuantizer (IxLS)
- IndexProductResidualQuantizer (IxPR)
- IndexProductLocalSearchQuantizer (IxPL)
- ResidualCoarseQuantizer (ImRQ)
- IndexAdditiveQuantizerFastScan (IRfs/ILfs/IPRf/IPLf)
- IndexIVFAdditiveQuantizerFastScan (IVLf/IVRf/NPLf/NPRf)
- IndexIVFAdditiveQuantizer (IwLS/IwRQ/IwPL/IwPR)
Reviewed By: mnorris11
Differential Revision: D99137777
fbshipit-source-id: bb4201f32b1268d66907f9a3f34eff869c80dc9c
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5020
The prior deserialization validation for training data in
`read_ScalarQuantizer` skipped size checks when `trained` was empty,
allowing inconsistent index state to be materialized.
This diff hardens `read_ScalarQuantizer` in three ways:
1. **Trained size validation**:
Replace the `if (!ivsc->trained.empty())` guard with two-branch
validation. For qtypes that require training data
(UNIFORM/NON_UNIFORM), an empty `trained` vector is only accepted
when the index header has `is_trained == false` (a legitimate
untrained index). When `is_trained == true`, the trained vector
must match the expected size. Qtypes that need no training (fp16,
bf16, 8bit_direct*) still require `trained.size() == 0`.
2. **Dimension cross-validation**:
Validate that `ScalarQuantizer::d` matches `Index::d` from the index
header. A mismatch indicates a corrupted file and could cause the
trained size check to accept a wrong size.
3. **is_trained consistency**:
When training data is present, validate that the index header
`is_trained` flag is true. A false flag with valid training data
indicates file corruption.
To support these cross-validations, `read_ScalarQuantizer` now takes
a `const Index&` parameter for access to the index header fields.
Untrained indices (created via `index_factory` but not yet trained)
are legitimately serialized with `is_trained=false` and an empty
`trained` vector. The existing `FAISS_THROW_IF_NOT(is_trained)` guards
in `IndexScalarQuantizer::search()` and related methods already prevent
querying such indices, so no additional query-time validation is needed.
Reviewed By: mnorris11
Differential Revision: D98924927
fbshipit-source-id: cbb9906e031c871cb8d2baa7bb9cb9d2c6834e03
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5019
The `qbs` field (query block size) is an `int` read from serialized
FastScan index files. A negative value causes `pq4_qbs_to_nq()` to loop
infinitely at search time because arithmetic right shift on a signed `int`
preserves the sign bit, preventing the loop variable from reaching zero.
Validate `qbs >= 0` immediately after reading it during deserialization in
all three affected index formats:
- `IndexPQFastScan` (fourcc "IPfs")
- `IndexAdditiveQuantizerFastScan` (fourccs "IRfs", "ILfs", "IPLf", "IPRf")
- `IndexIVFAdditiveQuantizerFastScan` (fourccs "IVRf", "IVLf", "NPLf", "NPRf")
This catches malformed or adversarial index files at load time with a clean
`FaissException`, rather than hanging during search.
`IndexIVFPQFastScan` and `IndexIVFRaBitQFastScan` are not affected because
they only serialize `qbs2`, which is `size_t` (unsigned).
Reviewed By: mnorris11
Differential Revision: D98815835
fbshipit-source-id: 40c5f39c84bcc553b7031c601832ef2c7d0a4d64
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5011
Add a deserialization-time check in `read_index_binary` that rejects
`IndexBinaryHash` data where `b` exceeds `code_size * 8`. Without
this validation, a malformed index can cause `BitstringReader::read()`
to access past the allocated code buffer during search, resulting in a
heap-buffer-overflow.
Reviewed By: mnorris11
Differential Revision: D98811392
fbshipit-source-id: 6847bce77be6edb66d87bd28a770c2af615868d3
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5009
Add deserialization-time validation for all three FastScan index types
(IndexPQFastScan, IndexAdditiveQuantizerFastScan, IndexRaBitQFastScan)
in `index_read.cpp`. A crafted or corrupted index file could previously
supply invalid quantizer parameters that would cause crashes or undefined
behavior when the index was later used for search.
The following checks are added at deserialization time for each FastScan
variant:
1. **M > 0 and ksub > 0**:
These quantizer dimensions are used as divisors and loop bounds in
`compute_float_LUT` and search kernels. Zero values would cause
division-by-zero or empty allocations followed by out-of-bounds access.
2. **bbs > 0 and bbs % 32 == 0**:
The block batch size (`bbs`) is used as a divisor (e.g. `ntotal2 /
bbs`) in search and is assumed to be aligned to 32 by the SIMD packing
logic. A zero value causes division-by-zero; a misaligned value causes
incorrect memory access patterns.
3. **ksub * M and ksub * M2 overflow**:
These products are used to size lookup tables and scoring buffers. A
corrupted file could set M2 to a huge value, causing `size_t` overflow
and subsequent under-sized allocations with out-of-bounds writes. The
existing `mul_no_overflow` helper is used to detect this.
Reviewed By: mnorris11
Differential Revision: D98787875
fbshipit-source-id: 76656f1c1bea4afe2d268dbd46af5a6b3a7b5932
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5008
Add deserialization-time validation in `index_read.cpp` for
AdditiveQuantizer-based indices, catching corrupt or malicious index
files early rather than crashing during search.
1. **Codebooks divisibility check in `read_AdditiveQuantizer`**:
`codebooks.size()` must be a positive multiple of
`total_codebook_size`. This catches obvious corruption without
needing the effective dimension.
2. **`validate_codebooks_size` helper**:
Checks `codebooks.size() >= effective_d * total_codebook_size`.
Called from `read_ResidualQuantizer` and `read_LocalSearchQuantizer`
with `d`, and from `read_ProductAdditiveQuantizer` with
`d / nsplits`.
3. **`d > 0` validation**:
Reject zero dimension in `read_AdditiveQuantizer`.
4. **ProductAdditiveQuantizer checks**:
- `d % nsplits == 0` in `read_ProductAdditiveQuantizer`
- Sub-quantizer `d == d_sub` in `read_ProductResidualQuantizer`
and `read_ProductLocalSearchQuantizer`
Existing tests updated to write correctly-sized codebooks so they
continue to reach their intended validation points.
Reviewed By: mnorris11
Differential Revision: D98767295
fbshipit-source-id: 95d8debbbb0f3822bae087a546a573e5c2c3c9dd
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5007
Add input validation to VectorTransform deserialization to defend against
invalid or malicious serialized data:
1. **Negative dimension checks**:
Reject `d_in < 0` or `d_out < 0` immediately after reading, before
any allocations depend on these values.
2. **Byte limit check on `d_in * d_out`**:
Use `mul_no_overflow` to safely compute the product and verify it
does not exceed the deserialization vector byte limit. This prevents
allocation of excessively large matrices from corrupt data. The
existing per-type-specific `d_out > 0` check in HadamardRotation is
removed as redundant (the power-of-2 check already implies `d_out > 0`).
3. **IndexIVFIndependentQuantizer dimension consistency**:
When an `IndexIVFIndependentQuantizer` has a VectorTransform, validate
that `vt->d_in == indep->d` and `vt->d_out == index_ivf->d`. A mismatch
indicates a corrupt or tampered index file and would cause incorrect
behavior at query time.
Reviewed By: mnorris11
Differential Revision: D98683628
fbshipit-source-id: 0101ee1aa956c346b614d26569c20d6b442210b4
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4997
Collectively validate ntotal, beam_factor, and max_beam_size during
deserialization to ensure allocation limits are honored, even when
those allocations occur in search context (ResidualCoarseQuantizer::search()).
Specifically, search() allocates O(beam_size * M * n) int32_t elements where
beam_size is derived from min(k * beam_factor, ntotal). With an adversarial
ntotal of 2^60 or a beam_factor of 1e10, these allocations exceed max_size()
and throw an uncaught std::length_error, terminating the process.
This diff adds three layers of protection:
1. read_ResidualQuantizer(): Validates max_beam_size > 0 and that
max_beam_size * M * sizeof(int32_t) fits within the configurable
deserialization vector byte limit.
2. ResidualCoarseQuantizer ("ImRQ") deserialization path:
Validates beam_factor <= 1000 to prevent int overflow in beam_size
computation, and validates ntotal * M * sizeof(int32_t) against the
byte limit since search() can allocate O(ntotal * M) when beam_size
is capped to ntotal.
Why 1000? The default beam_size is 4 (expand candidate serarch by 4x).
A value of even 1000 makes no practical sense as in most cases it will
be equivalent to an exhaustive search (beam_size = -1), but is sufficient
to prevent overflow.
3. ResidualCoarseQuantizer::search():
Replaces bare arithmetic with mul_no_overflow() for the codes and
beam_distances allocations, so any overflow throws a catchable
FaissException instead of silently wrapping and causing undefined
behavior.
Reviewed By: mnorris11
Differential Revision: D98169828
fbshipit-source-id: a8cd067ebb0fcb3ca25bed80a6d2ccc0cdbc0a32
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4959
The link with the original diff D96943554 was lost for some reason, so reviving
So far the with_simd_level function would assume that all implementations are available for each function. This is not the case, and is effectively not the case when we enable AVX512_SPR.
This diff has a specialized with_selected_simd_levels that takes a bitmask of the available implementations as template parameter.
The previous with_simd_level remains, it assumes by default the AVX2, NEON and AVX512 implementations are available.
Reviewed By: algoriddle
Differential Revision: D97247328
fbshipit-source-id: 47367cda5ed4e4c02b095343878049caa47c9d38
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4984
Add two input validation checks when deserializing IndexBinaryMultiHash
("IBHm") from untrusted index files:
1. **b > 0**:
The `b` field specifies the number of bits extracted per hash
map. During search, `BitstringReader::read(b)` is called for each hash
map to extract hash values from query vectors. If `b` is zero or
negative, `read(0)` produces undefined hash values and the hash lookup
silently returns garbage results. This mirrors the existing `b > 0`
validation already present for IndexBinaryHash ("IBHh").
2. **nhash * b <= code_size * 8**:
The search path in `search_1_query_multihash()` creates a single
`BitstringReader` over the query vector and sequentially reads `b` bits
`nhash` times, consuming `nhash * b` total bits. The vector buffer is
`code_size` bytes ('= d/8'), providing `code_size * 8` bits. If `nhash
* b` exceeds this, the reader advances past the buffer boundary,
triggering an out-of-bounds read. The constructor already enforces
`nhash * b <= d`, but deserialization skipped this check, allowing
a crafted file to bypass the constraint.
Both checks use FAISS_THROW_IF_NOT_FMT to throw descriptive exceptions
with the invalid values, consistent with the existing nhash > 0 validation
in the same code path.
Reviewed By: mnorris11
Differential Revision: D97990226
fbshipit-source-id: 62d2f8f79e02f6d473676e90981d201ef57a2e00
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4980
IndexBinaryIVF::search dereferences invlists via
invlists->prefetch_lists() without any prior null check. The invlists
pointer can legitimately be nullptr through multiple paths:
1. Default construction: IndexBinaryIVF::invlists is initialized to
nullptr (IndexBinaryIVF.h:35) and the default constructor is
defaulted, leaving it null.
2. Deserialization with IO_FLAG_SKIP_IVF_DATA: When this flag is set,
read_InvertedLists_up returns nullptr, and the binary IVF reader
at index_read.cpp:2130 stores it directly (ils.release() on a null
unique_ptr yields nullptr). This is intentional — the flag allows
loading index metadata without the (potentially large) inverted
list data.
3. Deserialization with fourcc "il00": The serialized data explicitly
indicates inverted lists were not stored with the IVF object
(index_read.cpp:453), returning nullptr.
Without this check, any of these cases would segfault on the
invlists->prefetch_lists() call. With this check, the caller receives
a clear FaissException explaining the misconfiguration.
This mirrors the existing null check in the float IndexIVF::search
(IndexIVF.cpp:312) which already guards against the same condition.
Reviewed By: mnorris11
Differential Revision: D97848088
fbshipit-source-id: 406abb870dfa093ffc3ce49ba65904bebe4763a2
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4979
These checks guard against invalid runtime state that would otherwise
cause undefined behavior or confusing errors during search operations.
They are not redundant with deserialization-time checks — they protect
against programmatic misuse at query time.
Specific validations and their consequences if absent:
1. get_distance_computer: Verify storage is IndexBinaryFlat via
dynamic_cast. Without this, a nullptr or wrong-type storage would
pass a garbage pointer to dispatch_HammingComputer, leading to
memory corruption. Deserialization already validates storage type,
but this also guards against programmatic construction with the
wrong storage type. Converted from FAISS_ASSERT (which aborts or
is compiled out) to FAISS_THROW_IF_NOT_MSG for safe error
propagation.
2. ntotal > 0 in base_level_only search: The entrypoint selection loop
constructs std::uniform_int_distribution<idx_t>(0, ntotal - 1).
When ntotal == 0, this becomes distribution(0, -1) — undefined
behavior per the C++ standard ([rand.dist.uni.int]). An empty
index is valid state that can arise after deserialization or
construction, but searching it in base_level_only mode must be
rejected.
3. num_base_level_search_entrypoints > 0: This is a public, user-
settable parameter (default 32). If set to 0, the entrypoint
selection loop at line 388 never executes, nearest[i] stays at -1,
and the downstream FAISS_THROW at line 397 fires with the
misleading message "Could not find a valid entrypoint" — obscuring
the actual misconfiguration. The early check provides an actionable
error message naming the offending parameter.
Reviewed By: mnorris11
Differential Revision: D97845054
fbshipit-source-id: d57d364889ce6a6bcfda741d6541c4cdbac44e85
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4978
Add validation checks for binary index types at deserialization time.
Without these checks, malformed index files can cause out-of-bounds
memory accesses, null pointer dereferences, and type confusion during
subsequent search or add operations.
- **`read_index_binary_header`** —
strengthen `d >= 0` to `d > 0 && d % 8 == 0` and add `code_size == d /
8`. Binary indices represent vectors as bit arrays with one bit per
dimension; all operations compute byte offsets via `d / 8`. A dimension
that is not a multiple of 8 causes integer truncation in `code_size =
d / 8`, making every vector stride too short and causing out-of-bounds
reads/writes in `add()`, `search()`, and distance computations. A `d =
0` causes division by zero. A mismatched `code_size` has the same effect
— vector data is strided by `code_size` bytes (`x + i * code_size`),
so a wrong value means every vector access is at the wrong offset.
- **`read_binary_hash_invlists`** —
validate `vecs.size() == ids.size() * code_size`. Each inverted list
entry in `IndexBinaryHash` pairs a vector ID with `code_size` bytes of
raw vector data. If `vecs` is shorter than `ids.size() * code_size`,
distance computations that iterate through the vector bytes using the
ID count as stride will read past the end of the `vecs` buffer.
- **`read_binary_multi_hash_map`** —
validate `id < ntotal` for each deserialized ID. IDs in the multi-hash
map index into the underlying `IndexBinaryFlat` storage array. An
out-of-range ID causes an out-of-bounds read when the vector is looked
up during search, either returning garbage distances or crashing.
- **IndexBinaryHNSW (IBHf) and IndexBinaryHNSWCagra (IBHc)** —
validate three consistency invariants:
1. `hnsw.levels.size() == ntotal`: The HNSW graph stores one level entry
per vector. A mismatch causes out-of-bounds reads in the levels array
during graph traversal, which runs inside OpenMP parallel regions.
2. Storage is `IndexBinaryFlat`: `get_distance_computer()` does
`dynamic_cast<IndexBinaryFlat*>(storage)` and dereferences the result.
A non-flat storage type yields a null pointer, crashing the process.
3. `storage->ntotal == ntotal`: HNSW graph node IDs index into the
storage. If storage has fewer vectors than the graph expects,
search traversal accesses out-of-bounds storage entries.
Reviewed By: mnorris11
Differential Revision: D97819033
fbshipit-source-id: 88787c05b9edae522217a65c86eacc3488696736
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4983
Validate that the `qb` (query quantization bits) field is valid for all
6 RaBitQ deserialization points (IndexRaBitQ, IndexRaBitQFastScan,
IndexIVFRaBitQ, IndexIVFRaBitQFastScan, and their multi-bit variants).
The `qb` parameter controls the scalar quantization precision of query
vectors in the RaBitQ algorithm.
- **'FastScan' formats: `qb = 0` is invalid for the quantized path.**
The quantized distance computer (`RaBitQDistanceComputerQ`) computes
`max_code = (1 << qb) - 1` and then divides by `delta = (v_max - v_min)
/ max_code`. With `qb = 0`, `max_code` is 0, producing a division by
zero. The `Z_MAX_BY_QB` lookup table is also indexed by `qb - 1`, so
`qb = 0` causes an out-of-bounds read from the 8-element array.
- **All other formats: `qb = 0` is valid and means "use unquantized float32 distance computation."**
When `qb == 0`, the code returns a `RaBitQDistanceComputerNotQ` that
operates on raw fp32 values without any scalar quantization of the query. Ixrq is the original/default 1-bit RaBitQ format and the only format that supports `qb==0`.
- **`qb > 8` overflows `uint8_t` quantized values.**
The query vector is scalar-quantized into `rotated_qq`, a
`std::vector<uint8_t>`, with values in `[0, (1 << qb) - 1]`. For `qb > 8`,
`(1 << qb) - 1` exceeds 255 and the cast to `uint8_t` silently
truncates, producing incorrect quantized values. The bit-rearrangement
loop in `set_query` also extracts individual bits via `rotated_qq[idim]
& (1 << iv)` for `iv` in `[0, qb)` — with `qb > 8` this shifts beyond
the 8-bit width of `uint8_t`, yielding undefined behavior.
- **Existing runtime checks are `FAISS_ASSERT`, not `FAISS_THROW`.**
Both `RaBitQDistanceComputerQ::set_query()` and
`compute_query_factors()` have `FAISS_ASSERT(qb > 0)` / `FAISS_ASSERT(qb
<= 8)` checks, but these compile to no-ops in release builds and call
`abort()` in debug builds. In either case, when reached inside an OMP
parallel region (as happens during search), `abort()` terminates the
entire process without cleanup. Validating at deserialization time
converts this into a catchable exception before the invalid value can
reach any parallel code path.
Reviewed By: mnorris11
Differential Revision: D97815297
fbshipit-source-id: 53fce4b8befe14bfd301451a125684c03e939b2b
Summary:
For some reason a refactor in my last commit of the Panorama HNSW PR removed the update of the heap threshold, so nothing was getting pruned (and hence there was no speedup)... 😓
This PR also adds PanoramaStats to HNSW and a unit test to avoid this from happening again.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4974
Reviewed By: subhadeepkaran
Differential Revision: D97980331
Pulled By: mnorris11
fbshipit-source-id: 9a74d9880439ddf313330dc03b6e3182563b3d1e
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4981
Validate internal consistency of VectorTransform data at deserialization
time to prevent crashes from malformed index files, leading to out-of-bounds
reads/writes.
- **HadamardRotation** — validate `d_out > 0` before calling `init()`.
`init()` calls `generate_signs(seed, d_out, …)` which `resize()`s three
`std::vector<float>` to `d_out` elements and then iterates over them.
A zero `d_out` would violate the `p > 0` assert inside `generate_signs`.
- **RemapDimensionsTransform** — validate `map.size() >= d_out`.
`apply_noalloc` loops `for (j = 0; j < d_out; j++) xt[j] = … x[map[j]]`,
indexing into `map` with `j`. If `map` is shorter than `d_out`, the loop
reads past the end of the vector, producing an out-of-bounds heap read
that can crash or leak memory contents.
- **CenteringTransform** — validate `mean.size() >= d_in`.
`apply_noalloc` loops `for (j = 0; j < d_in; j++) *xt++ = *x++ - mean[j]`,
so a `mean` vector shorter than `d_in` causes an out-of-bounds read on
every input vector processed.
- **ITQTransform** — validate `mean.size() >= d_in`.
`apply_noalloc` subtracts `mean[j]` for `j` in `[0, d_in)` before
passing the normalized data to the PCA+ITQ chain. The same out-of-bounds
read hazard as CenteringTransform applies here.
Reviewed By: mnorris11
Differential Revision: D97809504
fbshipit-source-id: da82d1c1b62d06b09b387d11a7934091b6754daf
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4951
Add null-pointer checks for `invlists` in `IndexIVF::add_with_ids()`,
`IndexIVF::search()`, and `IndexIVF::search_preassigned()`.
When an IVF index is deserialized with `IO_FLAG_SKIP_IVF_DATA`, the
`invlists` pointer is null. Calling add or search on such an index
would dereference the null pointer, causing a crash. These checks
provide a clear error message instead.
Reviewed By: mnorris11
Differential Revision: D96967039
fbshipit-source-id: 288ee0964b5d9fffbf617d0d826b8182a46f7de9
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4950
When `IndexHNSWCagra::search()` is called with `base_level_only=true`
on an empty index (`ntotal == 0`), it proceeds to create entry point
vectors and access random graph nodes, causing undefined behavior.
Add an early return that fills the output arrays with sentinel values
(max float distances and -1 labels) when the index is empty, consistent
with how other FAISS index types handle empty-index queries.
Reviewed By: mnorris11
Differential Revision: D96966891
fbshipit-source-id: 0b9cded2e0e14ad6e4b0869cce4da1311e595d96
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4949
Add validation checks for graph-based index types during deserialization:
- NNDescent: validate that `final_graph` size matches `ntotal * K` and
that all neighbor IDs are in the valid range `[-1, ntotal)`.
- HNSW: cross-check that `hnsw.levels.size()` matches the index header
`ntotal`, and that the storage sub-index `ntotal` and `d` match the
parent index.
- NSG: cross-check that `nsg.ntotal` matches the index header `ntotal`
(when built), and that the storage sub-index `ntotal` and `d` match.
- NNDescentFlat: cross-check that `nndescent.ntotal` matches the index
header `ntotal` (when built), and that the storage sub-index `ntotal`
and `d` match.
These checks catch corrupt or maliciously crafted index files that could
cause out-of-bounds memory access during graph traversal in search.
Reviewed By: mnorris11
Differential Revision: D96966646
fbshipit-source-id: a3839e84884c45221aa8608cb1f4271eea7ca05e
Summary:
- Fix compiler warnings in all 20 FAISS C++ test files
- Fixes include `-Wshadow`, `-Wunused-parameter`, and signed/unsigned comparisons
All changes are mechanical. No functional changes.
Part 13/13 of the compiler warnings cleanup (split from https://github.com/facebookresearch/faiss/issues/4810 per maintainer request).
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4944
Test Plan:
- [x] No functional changes — all fixes are mechanical renames and annotations
🤖 Generated with [Claude Code](https://claude.com/claude-code)
Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
Reviewed By: mnorris11
Differential Revision: D96996609
Pulled By: alibeklfc
fbshipit-source-id: 72555246a4ccf540eb5422e64018c8d5e2660dce
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4948
Add validation that the deserialized codes vector size matches
`ntotal * code_size` for the following index types: IndexPQ,
IndexResidualQuantizer, IndexLocalSearchQuantizer,
IndexProductResidualQuantizer, and IndexProductLocalSearchQuantizer.
A mismatch between the codes vector size and the expected size from the
index header indicates a corrupt or maliciously crafted index file. Without
this check, a truncated or inflated codes vector would cause out-of-bounds
memory access during search or reconstruction operations.
Reviewed By: mnorris11
Differential Revision: D96966390
fbshipit-source-id: 37602d0343f0d79a07487c7f54ed45fd09ae45dd
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4961
Replace unsafe *(uint64_t*) casts with BitstringReader in all 4 hash
computation sites in IndexBinaryHash and IndexBinaryMultiHash. The old
casts read 8 bytes regardless of code_size, causing out-of-bounds reads
for small vectors (e.g., code_size=2 for d=16).
BitstringReader reads only the needed bits byte-by-byte.
Reviewed By: mnorris11
Differential Revision: D97317369
fbshipit-source-id: 07436583d15bef8546afe4e4c2d19586d93e6d37
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4954
Two tests — test_batch_boundaries and test_incremental_add — generated random
data (xt, xq, xb) using np.random.rand() without setting a random seed first.
This made the test data non-deterministic across runs. Occasionally, the random
data would produce vectors with very similar distances, causing slight
floating-point ordering differences between Panorama and regular IVFFlat that
pushed the overlap rate below the 0.999 threshold.
Update both tests to use a fixed random seed for all random data generation.
Reviewed By: mnorris11
Differential Revision: D97127668
fbshipit-source-id: 380cd9fe533c80a8dfd8f8ba373b17070f2c0fbe
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4947
Add validation checks during index deserialization for quantizer data:
- ProductQuantizer: verify that the centroids vector size matches
`d * ksub`. A mismatch indicates a corrupt or maliciously crafted
index file and would cause out-of-bounds reads during search.
- ScalarQuantizer: verify that the trained vector size matches the
expected size for the quantizer type and dimension. The expected size
depends on the quantizer type (e.g., 2*d for per-dimension types,
2 for uniform types, 0 for direct/fp16/bf16 types).
Reviewed By: mnorris11
Differential Revision: D96965538
fbshipit-source-id: b64a2e316b5fcdf1cebefe6ffa6081bab2ecc640
Summary:
Following the suggestion in https://github.com/facebookresearch/faiss/issues/4848, this adds CappedInvertedLists which:
- Caps list_size() to maxsize (partial scan instead of skip)
- Allows writes (passes through to underlying invlists)
- Provides real_list_size() to query actual size
Unlike StopWordsInvertedLists which skips large lists entirely, this caps each list while maintaining partial recall from all clusters.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4880
Reviewed By: mnorris11
Differential Revision: D96039869
Pulled By: limqiying
fbshipit-source-id: 7964c5d14c49148c9a1c7c26668b48a6ebb784a8
Summary:
This PR introduces the following:
* a new type of a `ResultHandler` called `SingleQueryResultCollectHandler`
* adds a filtering capability to the core of the FastScan code
* `SIMDResultHandler::size_t in_range_num` and `SIMDResultHandlerToFloat::scan_cnt`, which can be effectively used for early stop checks. These are not currently used in the baseline `FAISS` code, but are used in the `Knowhere` fork
mdouze mnorris11 junjieqi please comment and suggest unit tests + locations that need to be written, given some possible unusual use cases on your end
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4926
Reviewed By: subhadeepkaran
Differential Revision: D96651396
Pulled By: mnorris11
fbshipit-source-id: c15bc1fc1398d072014315187c9e4dd98c573190
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4928
The original intention of the `READVECTOR` and `READXBVECTOR` macros in
`io_macros.h` was to limit reads to 256GB (see comment above the previous
version of READVECTOR). However, the enforced limit was actualy based on
element count not bytes, allowing extremely large reads — requiring TBs of
memory — to pass the check and be attempted.
In this diff, represent the limit in bytes, and set the default value to
1TB. This value can be changed at runtime via the
set_deserialization_vector_byte_limit() API.
Reviewed By: mnorris11
Differential Revision: D96559593
fbshipit-source-id: 38937c912aa5f7e17c45aed6f37b1bfd1b5b3e1a
Alibek Zhakubayev