711 Commits

Include renames

Author	SHA1	Message	Date
Alibek Zhakubayev	07979b10e6	Randomized Ball Carving partition (#5714) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5714 We add the Randomized Ball Carving partition, which splits the dataset into small overlapping leaves, and `gather_rows`, which reads rows of the storage as floats for the kernels. **Motivation** The PiPNN graph build (Rubel et al., "PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing", KDD '26, arXiv:2602.21247) first partitions the dataset into small overlapping leaves, then builds candidate edges inside each leaf. The partition must read the vectors exactly as search sees them, whatever the storage. It must produce the same leaves for any thread count, so that builds are reproducible, and its memory must stay bounded at billion scale. It must also terminate on degenerate data, such as duplicate points, or inner-product data where one high-norm leader attracts every point. **Implementation** - `faiss/impl/pipnn/kernels.{h,cpp}`: `gather_rows(storage, ids, k, out)` reads rows with `reconstruct()`, except `IndexScalarQuantizer` rows, which it decodes with one `SQuantizer` per call. We do not use `sa_decode` or `reconstruct` for SQ storage: `ScalarQuantizer::decode` opens an OpenMP region, and a nested region inside the partition's `schedule(dynamic)` loops segfaults with the libomp of fbcode builds. - `faiss/impl/pipnn/Partition.{h,cpp}`: Randomized Ball Carving (paper Alg. 5) with multi-level fanout. A root level runs first, then memory-bounded waves of root children. Each wave runs level-synchronous `omp for schedule(dynamic)` item lists that mix stripe items (one single-threaded `stripe_assign` call per 1024-point stripe) and leaf items, which are handed to a `LeafVisitor`. Each level runs four steps that share a `LevelContext`: `plan_level` (leaders and work items), `assign_leaders` (the stripe and leaf loop), `scatter_children` (the counting sort below) and `collect_children` (the merge and degenerate-child rules). - A per-block counting sort scatters the children, so every child lists its points in parent order. Small children are merged in a seeded Fisher-Yates order. An IP-ranked child that holds more than 90% of its parent is re-partitioned by L2, and a child equal to its parent or at the depth limit is cut into id slices. Together these rules guarantee termination. - Leader sampling (Floyd's algorithm), the merge order and every child seed come from `SplitMix64RandomGenerator` and `mix_seed`, and every selection uses a strict total order, so the leaves do not depend on the thread count or on the wave budget. - The stripe and leaf loop captures exceptions per item and rethrows them after the loop. Its master thread polls `InterruptCallback` after its first item and then every 64 items, and the partition checks it between levels. A throwing `InterruptCallback` is captured like any item exception. The classify loop also captures and rethrows exceptions; the counting-sort loops cannot throw. - Memory: the per-level assignment, count and child-id arrays are uninitialized heap arrays, so they are not zero-filled before being overwritten. The per-level node and work-item lists are reserved heap vectors, proportional to the number of nodes in the level. Every partition buffer is released on exit, including on the throwing paths. We reject `c_max > 4096`, because each thread holds a `c_max` x `c_max` float matrix for its leaves. - The `test_pipnn_cpp` test target gains the `openmp` dependency, because the tests include `omp.h` to set the OpenMP thread count. - No caller yet outside the tests. The graph build uses this code in a later diff of the stack. Reviewed By: mnorris11 Differential Revision: D123103150 fbshipit-source-id: df2b82457f9c9840846a4707847f37bf03266ac7	2026-10-09 17:06:32 -07:00
Weixiang Hong	f46050eb56	Deflake test_io TestIVFPQRead.test_reader (#5718) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5718 `test_reader` searches one IVFPQ index loaded twice, with and without the precomputed table, and required the neighbor ids to be identical. The two paths add the distance terms in a different order, so near-tied neighbors can swap. With unseeded data it failed in 7 of 400 random draws, and once in seven runs of the Cogwheel faiss suite on T1_BGM (2 of 10000 ids). Compare with `check_ref_knn_with_draws`, which allows swaps only among tied distances, and seed the data so a failure reproduces. `test_io` moves to `py_tests_with_contrib` for the helper. Reviewed By: mnorris11 Differential Revision: D124383290 fbshipit-source-id: ceb81262ffaba81ac23e5a592e1658741192060d	2026-10-09 16:25:26 -07:00
Eppalapelly Madhukar	8b884ecc96	Fix IndexFastScan::reset() leaving stale ntotal2 (crash on search) (#5614) ... Summary: reset() cleared ntotal and the codes buffer but left ntotal2 (the bbs-padded scan count) unchanged. A search after reset then scans ntotal2/bbs blocks over the freed, empty code buffer, dereferencing a null pointer in the SIMD kernel and crashing with SIGSEGV (Fixes https://github.com/facebookresearch/faiss/issues/5591). Clear ntotal2 in reset() too, matching init_fastscan(). This covers all flat FastScan indexes (PQ/AQ/RaBitQ), which share this reset(). Add test_reset reproducing train -> add -> reset -> search: it checks ntotal2 == 0 after reset and that searching the emptied index is safe and returns the -1 sentinel. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5614 Reviewed By: junjieqi Differential Revision: D124253538 Pulled By: mnorris11 fbshipit-source-id: 038186130c03534fc353eae9390f031413a05a5e	2026-10-08 22:43:31 -07:00
Michael Norris	2839c39f20	Make the GPU IVF search return the same neighbours on every run (#5682) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5682 This diff adds an option, `deterministic_tie_break`, that makes a GPU IVF search return the same neighbours on every run. It is off by default. **CHANGES THAT APPLY BY DEFAULT. No option turns these off. The id tie break itself is the new option `deterministic_tie_break`, which is off by default.** 1. **Tie order:** the interleaved IVF scan (`GpuIndexIVFFlat`, `GpuIndexIVFScalarQuantizer`) orders an exact distance tie by the position in the list, for `k` up to 1024. Before, the order followed the arrival order in the sort network. Only the choice among exactly equal distances can change. REASON: it blew up binary size to make it not like this. see below. 2. **Launch shape:** the first pass of the `k <= 32` interleaved scan runs with 64 threads in a block instead of 128. Measured on one A100 with `deterministic_tie_break` off: 1.8% faster than master. REASON: perf improvement. 3. **Padding:** pass 2 of the interleaved scan rejects the padding slots of a list shorter than `k`. On master a pad cannot win, because `Comparator` is strict. The tie order of item 1 lets a pad win a tie with the heap sentinel, so this check goes with item 1. REASON: used for deterministic, but should have no impact on non deterministic flow. 4. **`copy_subset_to` with `SUBSET_TYPE_ID_MOD`:** a vector with a negative id goes to the subset that its id selects. Before, it was dropped from every subset, and a multi-GPU clone with `shard_type` 1 failed its `ntotal` check. REASON: bug fix. 5. **`merge_knn_results`** (used by `IndexShards` and `IndexShardsIVF`): only `-1` marks a missing result. Before, every negative id did, so a sharded search with signed ids lost results. REASON: bug fix. 6. **Shared k-selection code** (`Select.cuh`, the merge networks): every comparison receives the value as well as the key. The default comparator ignores the value, so the results do not change. REASON: used for deterministic, but should have no impact on non deterministic flow. Below changes do not change the default results: - The RAFT `TieBreak` template parameter defaults to false, and generates the same code as upstream. - The new cuVS `search_params::select_algo` defaults to `kAuto`. **Behaviour before:** - A query whose candidates tie on distance can get a different neighbour on a second run. - `copy_subset_to` with `SUBSET_TYPE_ID_MOD` drops every vector with a negative id from every subset. - `merge_knn_results`, which `IndexShards` and `IndexShardsIVF` use, treats every negative id as a missing result. It drops a shard's results from its first negative id onward. - The `k <= 32` IVF scan runs its first pass with 128 threads in a block. **Behaviour after:** - With `deterministic_tie_break` on, a repeated search returns the same ids and the same distances. - With `deterministic_tie_break` off, the search behaves as before. Only the choice among exactly equal distances can differ from master, as it can between any two layouts. - `SUBSET_TYPE_ID_MOD` keeps a vector with a negative id, in the subset that its id selects. - `merge_knn_results` treats only `-1` as a missing result, so a sharded search returns negative ids. - The `k <= 32` IVF scan runs its first pass with 64 threads in a block. **Gating:** - `GpuIndexIVFConfig::deterministic_tie_break` and `GpuClonerOptions::deterministic_tie_break` default to false. The cloner copies `GpuClonerOptions::deterministic_tie_break` into the IVF config. The caller sets it when it creates or clones the index. - These indexes honour `deterministic_tie_break`: - `GpuIndexIVFFlat` and `GpuIndexIVFScalarQuantizer` with the interleaved layout, which is the default, for `k` up to 1024. This path needs no cuVS change. - The cuVS `GpuIndexIVFPQ` and the cuVS `GpuIndexIVFScalarQuantizer`, for `k` and `nprobe` up to 256, in a build that defines `FAISS_CUVS_HAS_STABLE_SELECT`. - The classic `GpuIndexIVFPQ` and cuVS IVF-Flat ignore `deterministic_tie_break`. - The interleaved scan ignores `deterministic_tie_break` above `k` = 1024. Its kernels for a larger `k` keep `Comparator`, because a tie break in their large merge networks costs much code size. - The cuVS indexes ignore `deterministic_tie_break` above 256, and in a build without the `FAISS_CUVS_HAS_STABLE_SELECT` macro. **Why the `FAISS_CUVS_HAS_STABLE_SELECT` macro exists:** - The cuVS path sets `search_params::select_algo` to `raft::matrix::SelectAlgo::kWarpDistributedShmStable`. - That field and that enum value exist only in a cuVS and RAFT tree that has the cuVS and RAFT changes in this diff. They are not in cuVS 26.02, and they are not upstream yet. - Code that names them does not compile against such a tree. The macro tells the compiler that the symbols exist. It does not turn `deterministic_tie_break` on. - The internal Buck build defines the macro for its patched cuVS 26.06 tree. The CMake build does not define it. - When upstream cuVS and RAFT have the symbols, a cuVS version check can replace the macro. **Why each change is needed:** - The GPU k-selection ordered on the distance alone, so an exact tie followed the order in which the data reached the sort network. - With `deterministic_tie_break` on, `TieBreakComparator` orders a tie by the user id, which the IVF pass-1 kernel carries as the value. Pass 1 loads an id only when its candidate can still enter the top `k`. - With `deterministic_tie_break` off, pass 1 keeps the list offset as before, and pass 2 translates the offset to the user id as before. - IVF pass 2 rejects the padding that pass 1 leaves in a short list. A padded slot could otherwise win a tie and reach the output. - `raft/util/bitonic_sort.cuh` and `raft/matrix/detail/select_warpsort.cuh` add a tie break on the payload index as a template parameter, `TieBreak`, false by default. With false, the generated code is the same as upstream. - The new RAFT selector `kWarpDistributedShmStable` uses the new class `warp_sort_distributed_ext_stable`, which sets `TieBreak` to true. It supports `float` and `half` keys, and fails for other key types, so their `select_k` instantiations do not grow. - cuVS `ivf_pq.hpp` and `ivf_sq.hpp` add `search_params::select_algo`, with the default `kAuto`. The IVF-PQ and IVF-SQ searches pass it to their `select_k` calls. With `deterministic_tie_break` on, faiss asks for `kWarpDistributedShmStable`. - A sharded index with signed ids lost about half of its neighbours. On one A100, 4 shards of an `IVF64,SQ8` index with 20,000 signed random ids agreed with the unsharded index on 28% to 29% of the neighbours, with the id split and with the list split. With the fix, they agree on 100%. - `copy_subset_to` tested `id % n == i`. C++ gives a negative remainder for a negative id, so the test never matched. The fold `((id % n) + n) % n` maps every id into `[0, n)`. - The first pass of the `k <= 32` scan is faster with 64 threads. The measurements follow. **A caller that wants a repeatable search must also do two things itself:** - Train the codec once and reuse it, because k-means is not repeatable. - Sort each inverted list by id after the build. cuVS IVF-PQ, cuVS IVF-SQ, and an index with `INDICES_CPU` or `INDICES_IVF`, break a tie on the position in the list, and position follows insertion order. **Build size:** - The RAFT tie break is a template parameter, so only the stable selector instantiates the tie-break code. The other `select_k` instantiations generate the same code as upstream. - The scan kernels for `k` above 1024 keep `Comparator`, because a tie break in their large merge networks costs much code size. - A local dev ASAN build of `libfaiss_gpu_faiss.so` is 829.3 MiB. The `.nv_fatbin` section is 265.1 MiB. - CI reports no build size or build speed regression signals. **Measurements** Every number comes from one A100 80GB unless otherwise noted, and an opt build: - Base: 2,000,000 vectors, d = 768, float32, uniform in `[0, 1)` from `np.random.RandomState(1234).rand`. - Queries: 20,000 vectors from the same generator. - Metric: L2. - Coarse quantizer: `IndexFlatL2` with `nlist` = 519, so a list holds about 3,850 vectors. Training uses the first 200,000 base vectors. - Timing: one `search` call over all 20,000 queries. QPS is 20,000 divided by the best wall time. - Noise: six builds of the unchanged code differ by 0.33%. *Classic GPU IVF scan.* `IndexIVFScalarQuantizer` with `QT_8bit`, cloned with `use_cuvs = False`. `k` = 10, `nprobe` = 16, 61,657 candidates for each query. Best of 3 searches, two runs for each build: | build | QPS | | --- | --- | | master | 7,740 / 7,732 | | this diff, `deterministic_tie_break` off | 7,862 / 7,878 | | this diff, `deterministic_tie_break` on | 7,857 / 7,861 | - `deterministic_tie_break` costs about 0.1%, which is inside the noise. - With `deterministic_tie_break` off, this diff is 1.8% faster than master. The gain comes from the 64-thread first pass. First-pass threads in a block, same data, `deterministic_tie_break` on: | threads | QPS | | --- | --- | | 32 | 7,240 | | 64 | 7,877 | | 128 (the master launch shape) | 7,493 | | 256 | 6,428 | 512 threads does not build: `FinalBlockMerge` has no specialisation for 16 warps. The 64-thread gain over 128 holds across shapes on A100, H100, GB300. The H100 and GB300 rows below ran with `deterministic_tie_break` off: ``` ┌───────┬─────┬─────┬────────┬────────────────────────────┬─────────────────────────────────────┬─────────────────┐ │ GPU │ d │ k │ nprobe │ 64 threads (run 1 / run 2) │ 128 threads, master (run 1 / run 2) │ gain │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 768 │ 10 │ 16 │ 15,726 / 15,691 │ 14,316 / 14,258 │ +9.9% / +10.1% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 768 │ 32 │ 16 │ 15,668 / 15,645 │ 14,273 / 14,228 │ +9.8% / +10.0% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 128 │ 10 │ 16 │ 144,849 / 145,020 │ 125,843 / 125,592 │ +15.1% / +15.5% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 768 │ 10 │ 64 │ 3,946 / 3,946 │ 3,585 / 3,580 │ +10.1% / +10.2% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 768 │ 10 │ 16 │ 16,627 / 16,629 │ 8,693 / 8,694 │ +91.3% / +91.3% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 768 │ 32 │ 16 │ 16,576 / 16,570 │ 8,670 / 8,672 │ +91.2% / +91.1% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 128 │ 10 │ 16 │ 157,620 / 157,534 │ 79,062 / 79,100 │ +99.4% / +99.2% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 768 │ 10 │ 64 │ 4,116 / 4,116 │ 2,167 / 2,167 │ +89.9% / +89.9% │ └───────┴─────┴─────┴────────┴────────────────────────────┴─────────────────────────────────────┴─────────────────┘ ``` A thread queue of 3 was 2.5% faster than 2 on the A100 and level on an H100, so this diff keeps 2. *cuVS IVF-PQ.* `GpuIndexIVFPQ` with `use_cuvs = True`, `M` = 384, 8 bits for each code, trained and filled on the GPU, copied to the CPU, then cloned twice: once with `deterministic_tie_break` off (`kAuto`) and once with it on (`kWarpDistributedShmStable`). Timed searches alternate between the two clones. Best of 5, two runs: | k | nprobe | `deterministic_tie_break` off | `deterministic_tie_break` on | cost | | --- | --- | --- | --- | --- | | 10 | 16 | 16,078 / 15,984 | 16,043 / 15,964 | +0.22% / +0.13% | | 100 | 64 | 3,967 / 3,965 | 3,988 / 3,960 | -0.52% / +0.11% | - The stable selector costs about 0.1% to 0.2%, which is inside the noise. - The two selectors returned different ids for 0.0015% to 0.045% of the results. These are exact distance ties: PQ sums table entries, so equal distances are more frequent than with raw floats. *cuVS IVF-SQ.* `GpuIndexIVFScalarQuantizer` with `QT_8bit` and `use_cuvs = True`, `INDICES_64_BIT`, built on the CPU, then cloned twice: once with `deterministic_tie_break` off (`kAuto`) and once with it on (`kWarpDistributedShmStable`). Timed searches alternate between the two clones. All 5 searches of both runs, in QPS: | run | k | nprobe | `deterministic_tie_break` off | `deterministic_tie_break` on | best off / best on | | --- | --- | --- | --- | --- | --- | | 1 | 10 | 16 | 14,189 / 14,290 / 14,359 / 14,311 / 14,321 | 14,252 / 14,266 / 14,337 / 14,340 / 14,245 | 14,359 / 14,340 | | 1 | 100 | 64 | 2,923 / 2,945 / 2,950 / 2,952 / 2,951 | 2,932 / 2,950 / 2,943 / 2,952 / 2,936 | 2,952 / 2,952 | | 2 | 10 | 16 | 14,232 / 14,290 / 14,288 / 14,259 / 14,143 | 14,219 / 14,280 / 14,278 / 14,184 / 14,301 | 14,290 / 14,301 | | 2 | 100 | 64 | 2,934 / 2,941 / 2,949 / 2,947 / 2,945 | 2,934 / 2,944 / 2,941 / 2,941 / 2,936 | 2,949 / 2,944 | - The best-of-5 difference is between -0.17% and +0.08%, which is inside the noise. - The two selectors returned different ids for 0.0090% (k = 10) and 0.0578% (k = 100) of the results, in both runs. These are exact distance ties. Reviewed By: alibeklfc Differential Revision: D121990149 fbshipit-source-id: ad68d32289da529356fc77a0737d3c637600f976	2026-10-07 14:12:31 -07:00
Fadi Arafeh	a2f7943005	Optimize 4-bit PQ fastscan accumulation on Arm CPUs (#5709) ... Summary: - FastScan's pq4 kernel uses vector abstractions that are 256-bit wide - e.g. `simd32uint8` and `simd16uint16` - These are performant for processors whose SIMD registers are 256-bits - However, on Arm, these are implemented using 2 128-bit NEON registers - which leads to register pressure - For example, the original algorithm which accumulates NQ queries x 32 db elements uses these accumulators: `simd16uint16 accu[NQA][4]` which add up to 24 Neon registers (for the common case where NQA=3) - out of a total of 32 avaliable NEON registers. - With other temp registers for code vectors and LUT, the compiler spills registers to stack This change: - Adds a native NEON kernel equivalent for `pq4_kernel_qbs_256` which accumulates NQ queries for a single basic block of 32 database vectors (it uses 12 accumulators for NQA=3) --- (we'll raise another PR for speeding up `kernel_accumulate_block` which accumulates NQ queries for multiple 32-vectoer DB blocks.) - keeps the existing QBS decomposition, PQ code packing, LUT packing and the PQ4 accumulate loop - this is now shared between the neon kernel and the existing simd256 kernel - removes 126 Lines of deadcode from `decompose_qbs.cpp` - please let me know if these were left for a reason. ## Tests: This change is covered by existing tests: `test_fast_scan`, `test_fast_scan_ivf`, `test_sq_fastscan`, `test_ivf_sq_fastscan` - all these tests path. Also measured R@1, R@10 and R@100 for index types below for baseline and this PR and made sure they're identical. ## End to End Performance: with topk=10, nprobe=64, Neoverse-V3 R@1, R@10 and R@100 match exactly with baseline | Dataset | Index | Threads | Speedup | |---|---|---:|---:| | sift1M | `PQ32x4fs` | 32 | **1.412x** | | sift1M | `PQ32x4fs` | 96 | **1.415x** | | sift1M | `PQ64x4fs` | 32 | **1.353x** | | sift1M | `PQ64x4fs` | 96 | **1.351x** | | sift1M | `PQ128x4fs` | 32 | **1.310x** | | sift1M | `PQ128x4fs` | 96 | **1.316x** | | sift1M | `IVF4096,PQ32x4fs` | 32 | **1.104x** | | sift1M | `IVF4096,PQ32x4fs` | 96 | **1.114x** | | sift1M | `IVF4096,PQ64x4fs` | 32 | **1.132x** | | sift1M | `IVF4096,PQ64x4fs` | 96 | **1.144x** | | sift1M | `IVF4096,PQ128x4fs` | 32 | **1.153x** | | sift1M | `IVF4096,PQ128x4fs` | 96 | 1.095x | | sift1M | `IVF4096,SQ4fs` | 32 | **1.156x** | | sift1M | `IVF4096,SQ4fs` | 96 | 1.082x | | sift1M | `IVF4096,RQ30x4fs_Nrq2x4` | 32 | **1.102x** | | sift1M | `IVF4096,RQ30x4fs_Nrq2x4` | 96 | 1.047x | | sift1M | `IVF4096,RaBitQfs` | 32 | 1.023x | | sift1M | `IVF4096,RaBitQfs` | 96 | 1.007x | | bigann10M | `IVF16384,PQ128x4fs` | 32 | 1.087x | | bigann10M | `IVF16384,PQ128x4fs` | 96 | 1.007x | Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5709 Reviewed By: junjieqi Differential Revision: D123883104 Pulled By: mnorris11 fbshipit-source-id: a97fa22b42c5ea238cc4220190a4e775a0a30eac	2026-10-07 13:10:01 -07:00
Alibek Zhakubayev	7069478c3f	Numeric kernels ... Summary: We add the numeric kernels of the PiPNN build. **Motivation** The PiPNN build spends its compute in three dense operations: assigning points to partition leaders, finding the k nearest neighbours inside each leaf, and computing per-point distance matrices for the final prune. Each one is a single BLAS product on a fixed block followed by a selection. The build must be deterministic across thread counts, so the output of each kernel must depend only on its inputs: the BLAS call must not thread internally, and every selection must use a strict total order. **Implementation** - Norms come from Faiss's `fvec_norm_L2sqr`, which gives a vector bitwise the same norm at any address. - `stripe_assign`: assigns each point of a stripe to its `fanout` nearest leaders under the L2, IP or Angle ranking. One `sgemm_` over rows pre-filled with leader norms, then a top-fanout in `(dist, leader_index)` order on a Faiss max-heap (`heap_replace_top` and `heap_reorder` with `CMax::cmp2`). NaN counts as +inf, no slot is ever skipped, and the output is `uint16` leader indices. Under Angle, a leader with a zero norm (all zeros, or underflowed in float) ranks +inf, after every leader with a nonzero norm. - `leaf_knn`: the k nearest neighbours of every point inside a leaf. One `ssyrk_` fills the lower triangle of the Gram matrix, distances are `max(0, ni + nj - 2G)` for L2 and `-G` for IP, and a symmetric pair scan selects in `(dist, local_index)` order without self pairs. Unfilled slots are -1 / +inf. - The top-k slots start as (+inf, `INT32_MAX`) rather than Faiss's (`FLT_MAX`, -1), so that +inf candidates still fill empty slots in index order; slots left empty become -1. - `pairwise_distances`: the full symmetric distance matrix for the final prune, with the same `ssyrk_` call and post-processing as `leaf_knn`. It uses its output as the Gram scratch and ignores its prior contents. - `kernels.h` states the determinism contract: callers invoke the kernels inside an active OpenMP parallel region, or from serial code only when `omp_get_max_threads() == 1` or OpenMP is disabled, so that each BLAS call runs single-threaded. It also lists the BLAS configurations that keep BLAS from threading on its own. The kernels never change BLAS threading settings. - No caller yet. The partition and the graph build use this code in later diffs of the stack. ___ Differential Revision: D123088771 fbshipit-source-id: 065e95c53321e1d74d377a5c8cd972bdc9cb024b	2026-10-07 10:42:50 -07:00
Alibek Zhakubayev	7a057952fd	HashPrune reservoir and sketch kernel (#5708) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5708 We add the HashPrune reservoir and its sketch kernel, the first building block of a PiPNN graph index (Rubel et al., KDD 2026, arXiv:2602.21247). **Motivation** PiPNN builds a navigable graph without beam searches during construction: it partitions the data into overlapping leaves, picks candidate edges inside each leaf, and keeps a bounded set of candidates per point with HashPrune. This diff adds only that per-point candidate set and the hash it buckets by. Its result must not depend on the order of offers, so that the build in a later diff can process leaves in parallel and stay deterministic. The rest of the stack adds, in order, the numeric kernels, the partition into leaves, the graph build, `IndexPiPNN` with search, and serialization with `index_factory` support. **Implementation** - `distance_key`: an order-preserving 16-bit key built from the scalar bf16 encoding. NaN maps to +inf and -0 to +0 on the bit pattern, which also holds under `-ffast-math`; the sign-magnitude to unsigned mapping makes signed inner-product distances compare correctly. - `ReservoirRef::offer`: the HashPrune insert over 8-byte slots kept sorted by hash. Bucket replacement, eviction and the farthest-slot scan all use the strict `(key, id)` order, so the final reservoir is a function of the set of offers, whatever their order. A full reservoir rejects an offer that is not below its cached maximum before the binary search, which is expected to be the common case at steady state. - `Hyperplanes` and `Hyperplanes::sketch`: Gaussian hyperplanes stored transposed and zero-padded, and a fixed-order `FAISS_NOINLINE` sketch kernel, so sketches computed on the fly are bitwise identical within one build. `residual_hash` derives the bucket bits. - `FAISS_NOINLINE` in `impl/platform_macros.h`. - No caller yet. The graph build uses this code in a later diff of the stack. Reviewed By: mnorris11 Differential Revision: D123079760 fbshipit-source-id: f4278cf1d960b1756cdd54b6fbb14dec6eca3b3c	2026-10-06 14:45:14 -07:00
Alibek Zhakubayev	d380b7d96c	Fix IndexFlatCodes::reset on mmap-loaded codes (#5707) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5707 `IndexFlatCodes::reset()` called `codes.clear()`. When the index was read with `IO_FLAG_MMAP_IFC` (or through a zero-copy reader), `codes` is a non-owning view, and `MaybeOwnedVector::clear()` asserts `is_owned`, so `reset()` aborted the process. This hits `IndexFlat`, `IndexScalarQuantizer` and every index that resets a flat-codes storage, e.g. `IndexHNSWFlat` and `IndexNSGFlat`. `reset()` now keeps `clear()` for owned codes (capacity is kept, as before) and replaces a view with an empty owned vector. The index can then be refilled with `add()`. ___ Differential Revision: D123073895 fbshipit-source-id: 892e07eaa81d0176e34769714292c036c772a4d7	2026-10-05 11:01:07 -07:00
Jaeyoon Jeong	b0074a3fa4	Add fp16 support to SuperKMeans (#5692) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5692 Accept packed IEEE fp16 rows through `SuperKMeans::train_ex`, widening bounded blocks directly into the existing fp32 rotated workspace. Route raw Float16 IVF training through SuperKMeans while preserving codec, mode, and metric boundaries, and expose the typed input through the low-level Python wrapper. Add direct, subsampling, multi-block, spherical, validation, IVF, codec-boundary, metric-boundary, and Python parity coverage. Reviewed By: mnorris11 Differential Revision: D122781442 fbshipit-source-id: fa31ef48ed32b6c7fedfad2dffe5dcef794cb618	2026-10-02 22:30:24 -07:00
Jaeyoon Jeong	e7c44eb000	Add AVX-512 fp16 conversion kernels (#5694) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5694 Add exact AVX-512 widening and fp32 accumulation specializations for packed fp16 data. Reuse the existing AVX-512 SIMD translation unit, expand runtime dispatch to the AVX-512 level, and cover conversion tails, large blocks, weighted and unweighted centroid updates, and architecture fallbacks. Reviewed By: mnorris11 Differential Revision: D122781509 fbshipit-source-id: 67cbc4546149f069706e80dd25cae25d3588b0cc	2026-10-02 18:24:52 -07:00
Jaeyoon Jeong	ae4466d57e	Avoid widening fp16 data for k-means++ initialization (#5693) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5693 Run `KMEANS_PLUS_PLUS` and `AFK_MC2` initialization directly from packed fp16 rows. Decode bounded per-thread row blocks, dispatch conversion once, and preserve the existing fp32 distance, RNG, and accumulation behavior without an `nx * d` fp32 copy. Reviewed By: mnorris11 Differential Revision: D122781508 fbshipit-source-id: d3ed17ff9903fd08eb0d1221a6c562c46af82ff8	2026-10-02 18:24:52 -07:00
ChenLiqing	ea29bac75d	RaBitQ: add batch-four estimates and 9-bit SIMD scoring (#5647) ... Summary: Extend RaBitQ's distance-computation API with four independent one-bit estimates and add optimized kernels for standard RaBitQ codes. - Add `RaBitQDistanceComputer::distance_to_code_1bit_batch_4`, with a default implementation that delegates to four single-code evaluations. - For non-centered, four-bit query quantization, reuse query bit planes across four database codes. The optimized kernel uses the existing `AVX512_VPOPCNT` dispatch level; other SIMD levels and query modes retain fallbacks. - Add AVX2 and AVX-512 full-distance kernels for 9-bit database codes, exploiting byte-aligned extra codes rather than scalar extraction. The scalar tail reads only the required extra bytes. - Add `-mbmi2` to the x86 SIMD compile flags in `xplat.bzl` and `CMakeLists.txt`. The `AVX2` and higher SIMD levels now require CPUID BMI2. The RaBitQ kernels call `_pext_u64` without `__BMI2__` guards. - Use local fixed-size `memcpy` for byte-aligned scalar bit-plane loads. ## API contract and scope Call `set_query()` before evaluating a batch. The four row pointers may be non-contiguous or repeated. Results are returned in input order. The method computes estimates only: it does not refine candidates, update thresholds, or increment search counters. Existing query modes and database precisions remain supported. No changes to HNSW traversal, filtering, graph construction, defaults, or serialized code layout are included. This is an opt-in batch API; existing search call sites are unchanged. ## Tests and benchmark New standalone tests cover batch/single agreement for database bits 1–9, query bits 0–8, both centering modes, L2/IP, available SIMD overrides, repeated/non-contiguous row pointers, query reuse, and unchanged statistics. Independent references check packed multi-bit values and unaligned/tail buffers, including exactly sized RBQ9 extra codes. A round-trip test checks stored codes and distances. `bench_rabitq_batch_estimates` compares four single-code estimates with the batch API at dimensions 128, 768, 960, and 1536. It prepares queries outside timing, shuffles code pointers, warms both paths, alternates measurement order, and prints per-code times and checksums. It is a scorer microbenchmark, not an end-to-end search benchmark. Local validation (GCC 12, Release dynamic-dispatch build, Intel Xeon Platinum 8375C): - Built `faiss_test` and `bench_rabitq_batch_estimates`. - 61 tests passed with `--gtest_filter='TestLowLevelIVF.*:*RaBitQ*:*HNSW*'`, including all five new tests. - 47 individual-process tests passed with `ctest -R 'RaBitQ|HNSW'`. - All five new tests passed with the changed RaBitQ translation units and test file instrumented by ASan/UBSan, including leak detection. Unchanged dependencies were linked from the Release build; this was not a fully instrumented library build. - Checked NONE, AVX2, AVX512 and AVX512_VPOPCNT on the local host. Clang 15 syntax checks passed for the three affected SIMD units, with baseline BMI2 disabled for the AVX2/AVX512 checks. ARM, non-BMI2 hardware, and native SPR execution were not performed locally. A CPU without BMI2 now uses the `NONE` level. - No on-disk format changes; code and distance round-trip checks passed. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5647 Reviewed By: junjieqi Differential Revision: D122390129 Pulled By: mnorris11 fbshipit-source-id: f3f1b1817e3fbcbf7896f3b4cf86eebcbba6f6b2	2026-10-02 07:58:02 -07:00
Evan Haque	76c0e01e0f	Add GPU-accelerated IVFPQ search to the Metal backend (#5449) ... Summary: This is a follow-up to https://github.com/facebookresearch/faiss/issues/5288, which added `MetalIndexIVFPQ` with GPU-resident storage while delegating search to the CPU. Adds GPU-accelerated IVFPQ search to the Metal backend, including optimized scanning through `M <= 64`. - Add Metal kernels for 8-bit PQ distance computation, inverted-list scanning, and top-k merging - Support optimized GPU scanning through `M <= 64` - Compute distance contributions only for PQ codes encountered in each list when `d <= 256` - Add a 32-thread cooperative kernel for lists containing at most 128 vectors - Retain the cached precomputed-LUT kernel for suitable `M <= 16` workloads - Stream precomputed terms for larger dimensions without allocating an `M * 256` threadgroup LUT - Support both L2 and inner product metrics - Add exact segmented top-k selection for inverted lists of any length - Add grouped multi-round merging without a fixed `nprobe * k` candidate limit - Compact invalid per-list padding before merging when lists contain fewer than `k` results - Reuse dynamically sized Metal scratch buffers across searches - Retain the legacy per-probe LUT path with optional FP16 lookup tables - Fall back to CPU search for unsupported configurations, search parameters, or Metal failures ## Changes - **Modified:** `MetalDistance.metal` - on demand PQ scans, large-M precomputed scan, short-list specialization, segmented top-k, and compacting grouped merge - **Modified:** `MetalDistance.h/.mm` - IVFPQ search orchestration and support for `M <= 64` - **Modified:** `MetalKernels.h/.mm` - dispatch for cached, on-demand, short-list, and large-M scan kernels - **Modified:** `MetalIndexIVFPQ.h/.mm` - GPU scan selection, reusable buffers, centroid uploads, precomputed terms, and CPU fallback - **Modified:** `MetalIndex.h` - add the `useFloat16` LUT configuration - **Modified:** `TestMetalIndexIVFPQ.mm` - direct-GPU scan validation and search-parameter fallback coverage ## Differences from CUDA IVFPQ **Training:** `MetalIndexIVFPQ::train` delegates training to its CPU index, as introduced in https://github.com/facebookresearch/faiss/issues/5288. CUDA can train the coarse and product quantizers on GPU. Training is a one-time cost. **Add path:** Coarse assignment, residual computation, and PQ encoding remain on the CPU. The encoded PQ codes are stored in GPU-resident Metal buffers. CUDA performs these operations on GPU. **Coarse quantization:** The coarse quantizer search runs on the CPU. The selected lists and coarse distances are passed to the Metal scan. **Distance computation:** For `d <= 256`, the preferred Metal path evaluates only the PQ codes encountered while scanning a list. This avoids constructing or loading all 256 lookup entries for every subquantizer, which is especially beneficial for short IVF lists. For other supported dimensions, Metal uses the CPU IVFPQ precomputed-table decomposition. The query-independent centroid/PQ term is computed once per trained index and the query term once per batch. **Threadgroup memory:** The existing cached lookup-table kernel remains available for suitable `M <= 16` workloads. Larger `M` values do not expand its `M * 256` threadgroup LUT, which would exceed Metal threadgroup-memory limits. Instead, they use the on-demand or streamed-precomputed scan paths. **List scanning:** Short lists use a 32-thread cooperative kernel with approximately 2 KiB of threadgroup scratch. Longer lists use segmented selection to maintain an exact running top-k. **Top-k merge:** Per-list results are merged in groups over multiple rounds. Invalid padding is compacted when lists contain fewer than `k` results. **Fallback:** The optimized scan supports `M <= 64`, `d / M <= 256`, and `k <= 512`. Unsupported configurations fall back to the legacy Metal path or CPU search. Search options that the GPU path cannot preserve, including selectors, scan budgets, and polysemous filtering, are forwarded to the CPU with their original parameters. ## Build and test ```bash cmake -B build \ -DFAISS_ENABLE_GPU=OFF \ -DFAISS_ENABLE_METAL=ON \ -DBUILD_TESTING=ON \ -DCMAKE_BUILD_TYPE=Release \ -DCMAKE_PREFIX_PATH="$(brew --prefix libomp)" \ . cmake --build build \ --target faiss faiss_metal TestMetalIndexIVFPQ \ -j$(sysctl -n hw.logicalcpu) cd build && ctest -R TestMetalIndexIVFPQ --output-on-failure ``` All six IVFPQ tests pass. Direct-GPU regression coverage exercises 800 combinations across `M=8,16,17,32,48,64`, L2 and inner product, `k` through 512, short and long lists, both merge modes, and 64-bit IDs. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5449 Reviewed By: junjieqi Differential Revision: D113864779 Pulled By: mnorris11 fbshipit-source-id: 741c12b2b014ef28a82569c6b0344352351a7325	2026-10-01 21:07:27 -07:00
lyang24	0db2f30886	rabitq neon kernels (#5532) ... Summary: This diff adds native ARM NEON kernels for the RaBitQ bitwise popcount operations and for the multi-bit inner product. The kernels replace the scalar fallbacks on ARM. They handle every supported bit width and every unaligned dimension. - `tests/test_rabitq_simd_neon.cpp` holds the correctness test, and `tests/BUCK` holds its `cpp_unittest` target. The target carries `target_compatible_with` on `ovr_config//cpu:arm64`, which mirrors the x86_64 gate on `test_rabitq_simd`. - `tests/test_rabitq_simd_util.h` holds the shared `kDims` list and the shared `random_bytes` helper. `test_rabitq_simd.cpp` and `test_rabitq_simd_dd.cpp` now use them too. - The three kernels that index a fixed array of eight accumulators assert `qb <= kMaxQueryBits`. `RaBitQuantizer::set_query` caps `qb` at 8, but the kernels are public templates and carry no other bound. The scalar kernel and the AVX-512 kernel need no such assertion, because they shift inside the loop and hold one accumulator. The multi-bit test compares with a relative tolerance of `2e-5`. The NEON kernel accumulates in eight lanes, so it does not reproduce the scalar sum bit for bit. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5532 Test Plan: `buck2 test fbcode//faiss/tests:test_ivf_index fbcode//faiss/tests:test_custom_result_handler fbcode//faiss/tests:test_hnsw fbcode//faiss/tests:test_rabitq_simd_neon fbcode//faiss/tests:test_params_override fbcode//faiss/tests:test_hnsw_rabitq fbcode//faiss/tests:test_rabitq fbcode//faiss/tests:test_search_params fbcode//faiss/tests:test_io_corrupted fbcode//faiss/tests:test_rabitq_utils`, run at the top of the stack on aarch64: 173 pass, 0 fail, 3 skip. `buck2 build fbcode//faiss:faiss` succeeds in the static aarch64 build and with `-c faiss.dynamic_dispatch=true`. The host holds Neoverse V2 cores with ASIMDDP, so `test_rabitq_simd_neon` runs its kernels natively rather than skipping. Reviewed By: alibeklfc Differential Revision: D121846717 Pulled By: mnorris11 fbshipit-source-id: de079613a52ced326045830fb799dfc9b169fe2e	2026-10-01 10:36:44 -07:00
lyang24	6c51305e64	Avoid double-advancing HNSW visited tables (#5596) ... Summary: The outer HNSW search loop called `vt->advance()` a second time. `HNSW::search` already ends with `vt.advance()` at `impl/HNSW.cpp:1861`, so the caller in `IndexHNSW.cpp` advanced the visited table once more per query. This diff removes that call and adds a comment that names the owner of the advance. The sibling call in `search_level_0` stays, because `search_level_0_impl` does not advance. **Microbenchmark.** The host holds 72 Cooper Lake cores. The build is `mode/opt`. One core is pinned, and the two binaries interleave over 5 rounds. The table reports the median of the medians. `IndexHNSWFlat`, `d=64`, `M=16`, `use_visited_hashset=false` to select the versioned array, one query for each iteration. | ntotal | before | after | ratio | |---|---|---|---| | 100k | 44.2 us | 44.2 us | 1.00x | | 400k | 63.8 us | 69.1 us | 0.92x | **The change gives no measurable speed gain.** Both rows sit inside a 10% to 27% spread. The arithmetic agrees: `visno` is a `uint8_t` that cycles from 1 to 254, so the code clears the table once for every 250 advances. Two advances for each query halve that interval, which costs about 800 extra bytes of memset for each query against a search of 44 us to 69 us. The value of the diff is the removal of a redundant call, not a speed gain. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5596 Test Plan: `buck2 test fbcode//faiss/tests:test_ivf_index fbcode//faiss/tests:test_custom_result_handler fbcode//faiss/tests:test_hnsw fbcode//faiss/tests:test_rabitq_simd_neon fbcode//faiss/tests:test_params_override fbcode//faiss/tests:test_hnsw_rabitq fbcode//faiss/tests:test_rabitq fbcode//faiss/tests:test_search_params fbcode//faiss/tests:test_io_corrupted fbcode//faiss/tests:test_rabitq_utils`, run at the top of the stack on aarch64: 173 pass, 0 fail, 3 skip. `buck2 build fbcode//faiss:faiss` succeeds in the static aarch64 build and with `-c faiss.dynamic_dispatch=true`. Reviewed By: alibeklfc Differential Revision: D121846632 Pulled By: mnorris11 fbshipit-source-id: 8928c4d4648ce061e63c084ded9c74fa17ef66bd	2026-10-01 10:36:44 -07:00
lyang24	76978eee4a	Fix selector handling for IVF iterator scans (#5592) ... Summary: Iterator-backed IVF scans ignored the configured `IDSelector`, and array-backed scans applied it. An iterator-backed scan therefore returned IDs that the selector excludes. `InvertedListScanner::iterate_codes` and `InvertedListScanner::iterate_codes_range` now test `sel` for every entry. `search_preassigned` also keeps the selector for an iterable list. The function clears `sel` when the selector is an `IDSelectorRange` that sets `assume_sorted`, because an array-backed list bounds a sorted section instead of testing every entry. An iterable list holds no contiguous section to bound, so it keeps the selector and takes the generic path. `range_search` holds no sorted-range shortcut and needs no equivalent change. The test loops over both values of `assume_sorted`, and it checks the KNN search and the range search. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5592 Test Plan: `buck2 test fbcode//faiss/tests:test_ivf_index fbcode//faiss/tests:test_custom_result_handler fbcode//faiss/tests:test_hnsw fbcode//faiss/tests:test_rabitq_simd_neon fbcode//faiss/tests:test_params_override fbcode//faiss/tests:test_hnsw_rabitq fbcode//faiss/tests:test_rabitq fbcode//faiss/tests:test_search_params fbcode//faiss/tests:test_io_corrupted fbcode//faiss/tests:test_rabitq_utils`, run at the top of the stack on aarch64: 173 pass, 0 fail, 3 skip. `buck2 build fbcode//faiss:faiss` succeeds in the static aarch64 build and with `-c faiss.dynamic_dispatch=true`. Reviewed By: alibeklfc Differential Revision: D121846696 Pulled By: mnorris11 fbshipit-source-id: 09c8a3673fea6cc53f3370f05f3b6d399dfb4548	2026-10-01 10:36:44 -07:00
lyang24	41023120df	Defer IVF list scan setup until needed (#5595) ... Summary: The IVF list scan prepared state that an early return then discarded. This diff moves `scanner->set_list`, the `ScopedCodes` fetch and the `ScopedIds` allocation after every check that can return first. A list that an `IDSelectorRange` excludes no longer builds a lookup table and no longer fetches its codes. The diff also folds the `jmin` offset into the initial codes pointer, and it replaces `std::unique_ptr<ScopedIds>` with `std::optional<ScopedIds>`. The diff also fixes a null-pointer dereference. `search_preassigned` cleared `sel` for a sorted `IDSelectorRange` before it tested `!(sel && store_pairs)`. That combination then reached `IDSelectorRange::find_sorted_ids_bounds`, which reads `ids[0]`. The `ids` pointer is null when the caller sets `store_pairs`. The test now runs before the code clears `sel`, so the combination throws. `IVF.sorted_range_selector_rejects_store_pairs` covers it. **Microbenchmark.** The host holds 72 Cooper Lake cores. The build is `mode/opt`. One core is pinned, and the two binaries interleave over 5 rounds. The table reports the median of the medians. `IndexIVFPQ`, `d=64`, `nlist=1024`, 100k vectors, `nprobe=1024`, sorted `IDSelectorRange`. | ids that pass the range | before | after | ratio | |---|---|---|---| | 1% | 836 us | 587 us | **1.43x** | | 10% | 894 us | 926 us | 0.97x | The gain grows with the number of lists that the range excludes. At 10% the saving sits inside the noise. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5595 Test Plan: `buck2 test fbcode//faiss/tests:test_ivf_index fbcode//faiss/tests:test_custom_result_handler fbcode//faiss/tests:test_hnsw fbcode//faiss/tests:test_rabitq_simd_neon fbcode//faiss/tests:test_params_override fbcode//faiss/tests:test_hnsw_rabitq fbcode//faiss/tests:test_rabitq fbcode//faiss/tests:test_search_params fbcode//faiss/tests:test_io_corrupted fbcode//faiss/tests:test_rabitq_utils`, run at the top of the stack on aarch64: 173 pass, 0 fail, 3 skip. `buck2 build fbcode//faiss:faiss` succeeds in the static aarch64 build and with `-c faiss.dynamic_dispatch=true`. Reviewed By: alibeklfc Differential Revision: D121846650 Pulled By: mnorris11 fbshipit-source-id: aa3d1d3e6f903ef9e57be5c3dd824a5b1a090228	2026-10-01 10:36:44 -07:00
Jaeyoon Jeong	38460ee969	Fix Faiss fp16 parity tests across architectures (#5695) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5695 Correct GPU tests to decode the exact packed fp16 values passed to `search_ex`; the generic software converter and legacy `roundToHalf` disagree on half-way ties. Keep labels exact while comparing CPU distances with the normal scaled `1e-5` BLAS/SIMD tolerance. ___ Differential Revision: D122785161 fbshipit-source-id: 057ded12bdc018add4bef39e514217b83b59c2cb	2026-10-01 07:33:29 -07:00
Jaeyoon Jeong	430a41ee4c	Native fp16 k-means training for Faiss IVF (#5671) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5671 Train IVF coarse quantizers from packed fp16 (IEEE binary16) data without an fp32 copy of the training set, and let the k-means assignment step consume fp16 natively. **k-means: `Clustering::train_ex(n, x, NumericType, index, weights)`** Float16 runs k-means directly on the fp16 rows, without a codec: - NaN/Inf check on the fp16 bit patterns - subsampling and random initialization copy fp16 rows - the centroid update accumulates fp16 rows into the fp32 centroids with F16C/NEON (`compute_centroids_fp16`) - the assignment step passes blocks of at most `decode_block_size` fp16 rows to `Index::search_ex(Float16)` Only k-means++ / AFK-MC2 initialization still widens the (subsampled) training set. **Assignment: `Index::search_ex(Float16)`** - Default for every index: widen bounded blocks and call `search()`. - `IndexFlat` (L2 / IP): the BLAS kernels take fp16 queries (`knn_L2sqr_fp16`, `knn_inner_product_fp16`). Queries are widened inside the kernel in chunks of at most 16 MiB, each reused for all database tiles; results are bit-identical to the fp32 path on the rounded queries. The AVX2 / AVX512 / SVE top-1 kernels share one templated body. Selectors, small inputs, d <= 32 and database-parallel searches widen chunks and use the fp32 path. `IndexFlat1D` and `IndexFlatPanorama` keep their own search. - GPU: every `GpuIndex` accepts Float16 (queries are copied to the device as fp16 and widened there); `GpuIndexFlat` with `useFloat16` storage searches fp16 queries directly with the fp16 GEMM. **IVF** - `IndexIVF::train_ex(Float16)` and `Level1Quantizer::train_q1_ex` use the native path; only the `train_encoder_num_vectors()` rows sampled for the encoder are widened. `IndexIVFFlat` trains only the coarse quantizer; `IndexIVFFlatDedup` rejects Float16. - `train_encoded` (IVF and Clustering) remains the generic codec path, e.g. for decode-time normalization. - `faiss::fp16_to_fp32` (faiss/utils/utils.h) is the shared bulk widening helper. **Performance** (opt build, AMD Genoa: F16C conversion only, no fp16 arithmetic) - top-1 knn, d=256, 65536 queries x 1024 centroids: fp32 22.2 ms, fp16 25.3 ms - k-means, 1024 centroids, 10 iterations: fp32 270 ms, fp16 319 ms, identical centroids On CPUs without fp16 arithmetic the GEMM still runs in fp32 on widened tiles, so fp16 is not faster than fp32 there. The gains are memory (fp16 data plus a bounded fp32 tile instead of a full fp32 copy) and a single hook (`search_ex`) for fp16-capable backends; GPU `useFloat16` already runs the fp16 GEMM directly. Reviewed By: mnorris11 Differential Revision: D121848262 fbshipit-source-id: 1400d3eeb7c713359895923dcb86c544570cba69	2026-10-01 04:06:09 -07:00
Michael Norris	fdb9535c15	Make search stats collection configurable (#5670) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5670 Follow-up to D121368933 and public PR https://github.com/facebookresearch/faiss/pull/5657. HNSW and RaBitQ search statistics are available to C++ and Python. Faiss collects them by default. Every search updates shared counters. Under high concurrency, these updates are expensive. In the 64-thread relaxed-atomic profile, `HNSWStats::combine_atomic` uses 74.14% of the sampled user cycles. This diff adds one process-wide flag in `faiss/utils/utils.h`: - `set_search_stats_enabled(bool)` - `get_search_stats_enabled()` The flag is a relaxed `std::atomic<bool>`. It is private to `utils.cpp`. The default is enabled, for backward compatibility. Callers that do not read the statistics can disable collection. Then the searches skip the global atomic updates. At the moment, the flag controls `hnsw_stats` and `rabitq_stats`. The name is generic on purpose. The other global stats objects (for example `indexIVF_stats`, `indexPQ_stats` and `indexPanorama_stats`) use plain `+=` on shared counters, so they have the same scaling problem. Later diffs can put these objects under the same flag without a new API. The documentation says that the values of global stats objects are unspecified when the flag is disabled. Thus, more coverage does not change the contract. API design: - Faiss often exposes a plain global for a setting, for example `distance_compute_blas_threshold`. This diff does not do that. The flag is for concurrent searches, and a thread can change it while other threads search. A plain `bool` is then a data race, and TSAN reports it. This stack fixed TSAN races in D121097648. - SWIG cannot wrap `std::atomic<bool>`. Thus, the setter and the getter are the only API. Python calls `faiss.set_search_stats_enabled(False)`. Other changes: - `bench_hnsw_stats` has a `stats` argument. `stats:0` disables collection, and `stats:1` enables it. One binary measures the two modes. - The tests save the flag value and restore it after the test. The C++ tests use `SearchStatsEnabledGuard`. The Python tests use `addCleanup`. Thus, a failed assertion does not change the flag for later tests in the same process. Mode/opt benchmark from V12, five sequential repetitions (mean real-time throughput): | External pthreads | Relaxed atomic stats enabled | Stats disabled | Change | | ---: | ---: | ---: | ---: | | 1 | 2.516 M/s | 2.411 M/s | 0.96x | | 2 | 3.919 M/s | 4.164 M/s | 1.06x | | 4 | 7.494 M/s | 8.260 M/s | 1.10x | | 8 | 12.717 M/s | 14.170 M/s | 1.11x | | 16 | 16.074 M/s | 22.979 M/s | 1.43x | | 32 | 19.929 M/s | 36.841 M/s | 1.85x | | 64 | 22.101 M/s | 66.642 M/s | 3.02x | The 0.96x value at 1 pthread is noise. A longer pinned measurement in the test plan shows no slowdown. At 1 thread, the atomic adds have no contention, so the expected gain is small. The disabled path scales 27.64x from 1 to 64 pthreads. The enabled path scales 8.78x. The disabled path does not scale linearly, because this one-vector search is very small. At 64 threads, the OpenMP runtime uses about 28% of the sampled cycles. Allocator, RTTI and shared-cache costs also contribute. Reviewed By: luciang Differential Revision: D121374405 fbshipit-source-id: a54ee81a68a63df01c93bd5098171658883cd5ab	2026-09-26 21:59:14 -07:00
Michael Norris	94a4331fee	Add reranked types to IndexSQFastScan and fix flat RaBitQ filtering (#5661) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5661 Two gaps in the flat fast-scan indexes, both found while benchmarking IDSelector filtering. `IndexSQFastScan` accepted only the native 4-bit quantizers. It now accepts the reranked types as well, the same set `IndexIVFSQFastScan` handles: QT_6bit, QT_8bit, QT_8bit_uniform, QT_8bit_direct and QT_8bit_direct_signed. Each code is SPLIT: the SIMD scan reads the top 4 bits, and `lo_codes` keeps the rest for rerank. The total is the quantizer's own width, so `SQ8fs` holds 8 bits per dimension, the same as plain `SQ8`. A flat index needs no direct map for this, unlike the IVF form, because the position is the id. `SQ8fs` and `SQ6fs` now resolve in `index_factory`. `IndexRaBitQFastScan` forwarded an `IDSelector` through every layer but its kernel never applied it, so a filtered search returned ids outside the admitted set. `RaBitQHeapHandler::handle` now tests the selector per code, after the SIMD block, which is where the PQ and SQ handlers test theirs. The entry point no longer refuses a parameter object. The type predicates and the nibble packing move to `impl/sq_fastscan_utils.h`. The flat and IVF classes then cannot disagree about which quantizers rerank, or about how a nibble is laid out. The `ISfs` payload gains the rerank factor and the original codes. Both are written for every quantizer, and the codes are empty for a native 4-bit index. `ISfs` has not been released, so no stored index is affected. Reviewed By: junjieqi Differential Revision: D121036639 fbshipit-source-id: 40e51fc348a483cf5da947fa7db56ff10f1af773	2026-09-25 13:47:19 -07:00
Michael Norris	ec94295adc	Bound the fast scan LUT scale by the accumulated sum (#5658) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5658 A fast scan kernel sums `M` uint8 table entries into a uint16 that can wrap around to 0. The scale that quantizes the table must therefore bound the whole sum that gets accumulated, not only one entry. Seven call sites each held their own copy of that rule. Only four applied it. This adds `quantize_lut::fastscan_lut_scale` and routes all seven through it. The bound also reserves a margin for `round_tab`, which rounds half up, so `n` terms can gain `n/2` over the unrounded sum. `IndexIVFRaBitQFastScan` also folds its per-probe bias into the bound, because that bias is rounded into the same accumulator. `IndexPQFastScan` only reaches the bound when a sub-vector holds one dimension. A nearest centroid keeps the selected entries near the bottom of each column. `IndexSQFastScan` sets `M = d`, so it fails above about `d = 512`. At `d = 1024` it goes from R@1 0.00 to 1.00. Search speed does not change. The scale is computed once per query, and the inner loop is untouched. An index at `M <= 256` quantizes to the same bytes as before, because the sum term does not bind there. Reviewed By: junjieqi Differential Revision: D120638521 fbshipit-source-id: 27d5dd15f5a60a9c80cec1f63f53ac9c6c51b8ff	2026-09-25 13:47:19 -07:00
anthony-zy	1768a5a8e9	Add RVV SIMD specialization for product quantizer distance-table computation (#5543) ... Summary: Add a RISC-V Vector Extension implementation for the product-quantizer distance-table computation, and wire it into the SIMD dispatch path. The kernels are runtime vector-length aware (vsetvl-driven, e32m1) rather than assuming a fixed vector width. Changes - compute_PQ_dis_tables_dsub2<RISCV_RVV> (utils/distances_rvv.cpp): RVV kernel for both inner-product and L2 dsub=2 distance tables. Centroids are first split into even/odd dimension planes (c0_all / c1_all) so each subquantizer's ksub entries load as contiguous vectors; the hot loop processes two subquantizers per iteration: IP: r = c0*x0 + c1*x1 (vfmul + vfmacc) L2: r = (c0-x0)^2 + (c1-x1)^2 (vfsub + vfmul + vfadd) - Add RVV specializations for the accompanying distance primitives: fvec_norm_L2sqr, fvec_L2sqr_ny, fvec_L2sqr_ny_transposed and fvec_inner_products_ny are vectorized (strided vlse32 over ny); the remaining fvec_* and VectorDistance specializations fall back to SIMDLevel::NONE. - compute_distance_tables / compute_inner_prod_tables: route dsub == 2 && nbits >= 3 && nbits < 8 through compute_PQ_dis_tables_dsub2 when COMPILE_SIMD_RISCV_RVV is defined, matching the AVX2 / ARM_NEON fast path. - compute_PQ_dis_tables_dsub2_dispatch: extend the dispatch mask to include RISCV_RVV. ### Review fixes The AI reviewers reported 6 valid defects. This version corrects all of them. - The RVV `compute_PQ_dis_tables_dsub2` unrolled the subquantizer loop by 2 and had no tail. An odd `M` left the last `ksub` table entries unwritten. The kernel now writes the last subquantizer in a tail loop. - `fvec_inner_products_ny<RISCV_RVV>` loaded every chunk from `y + j`. The base pointer missed the `i * d` offset. Each chunk after the first repeated the first vectors. The kernel now loads from `y + i * d + j`. - `fvec_norm_L2sqr<RISCV_RVV>` ran one `vfredusum` per vector chunk. A `d=768` input at VLEN=128 cost 24 serialized reductions. The function again keeps a tail-undisturbed accumulator, and it reduces once after the loop. - The `dsub2` kernels require `ksub % 8 == 0`. The dispatch condition accepted every `nbits < 8`, so an `nbits` of 1 or 2 made `compute_distance_tables` throw. The condition now also requires `nbits >= 3`. This defect also affected the AVX2 and the ARM NEON paths. - `search_sdc` dropped the per-thread `q_row` pointer precomputation. That change added `M` multiplications per database vector on every architecture. This version restores the precomputation. - The `ny` kernels fixed the chunk width at the VLEN=128 value. They now read `VLMAX` with `vsetvlmax`. Hardware with a larger VLEN uses the whole vector register. The diff also removes 2 unreadable comments from the RVV kernel. Caveat: the benchmark below ran on the previous version. That version included the `search_sdc` change that this version reverts. ### Performance (sg2044) Cmd: 1M 768 <PQ> 32 100 16 1 1000 1 <metric> (search ns/query, lower is better) | # | CONFIG | M | NPROBE | METRIC | F1(ns) | PQ1(ns) | F2(ns) | PQ2(ns) | Δ_PQ% | Δ_F% | |----|----------|-----|--------|--------|---------|---------|---------|---------|---------|--------| | 01 | PQ8x4 | 4 | 8 | L2 | 6656870 | 536988 | 6582134 | 495970 | -7.64% | -1.12% | | 02 | PQ8x4 | 4 | 8 | IP | 6228497 | 475320 | 6164081 | 481118 | +1.22% | -1.03% | | 03 | PQ8x8 | 8 | 8 | L2 | 6626171 | 545230 | 6580586 | 500343 | -8.23% | -0.69% | | 04 | PQ8x8 | 8 | 8 | IP | 6228452 | 519710 | 6165707 | 479864 | -7.67% | -1.01% | | 05 | PQ8x16 | 16 | 8 | L2 | 6615305 | 697070 | 6582239 | 624059 | -10.47% | -0.50% | | 06 | PQ8x16 | 16 | 8 | IP | 6227067 | 642949 | 6164572 | 587271 | -8.66% | -1.00% | | 07 | PQ8x32 | 32 | 8 | L2 | 6624323 | 1185655 | 6581329 | 902298 | -23.90% | -0.65% | | 08 | PQ8x32 | 32 | 8 | IP | 6239930 | 1155545 | 6164198 | 785403 | -32.03% | -1.21% | | 09 | PQ8x64 | 64 | 8 | L2 | 6624196 | 2006275 | 6578815 | 1687191 | -15.90% | -0.69% | | 10 | PQ8x64 | 64 | 8 | IP | 6225719 | 1800678 | 6164767 | 1512760 | -15.99% | -0.98% | | 11 | PQ8x96 | 96 | 8 | L2 | 6617525 | 3108377 | 6582946 | 2701758 | -13.08% | -0.52% | | 12 | PQ8x96 | 96 | 8 | IP | 6239711 | 2657958 | 6170006 | 2320803 | -12.68% | -1.12% | | 13 | PQ8x384 | 384 | 8 | L2 | 6620602 | 14029275| 6583820 | 12318712| -12.19% | -0.56% | | 14 | PQ8x384 | 384 | 8 | IP | 6228776 | 12089134| 6166143 | 10509785| -13.06% | -1.01% | | 15 | PQ8x32 | 32 | 4 | L2 | 3321625 | 773663 | 3298874 | 491225 | -36.51% | -0.68% | | 16 | PQ8x32 | 32 | 16 | L2 |13223858 | 2184906 |13152640 | 1645444 | -24.69% | -0.54% | | 17 | PQ8x32 | 32 | 32 | L2 |26430233 | 3405062 |26331426 | 3138563 | -7.83% | -0.37% | | 18 | PQ8x64 | 64 | 4 | L2 | 3320850 | 1191054 | 3298426 | 969309 | -18.62% | -0.68% | | 19 | PQ8x64 | 64 | 16 | L2 |13207340 | 3944868 |13149902 | 3252654 | -17.55% | -0.43% | | 20 | PQ8x64 | 64 | 32 | L2 |26467696 | 6725098 |26335327 | 6667493 | -0.86% | -0.50% | | 21 | PQ8x16 | 16 | 4 | L2 | 3316496 | 427653 | 3304051 | 367407 | -14.09% | -0.38% | | 22 | PQ8x16 | 16 | 16 | L2 |13203491 | 1198002 |13150061 | 1121421 | -6.39% | -0.40% | | 23 | PQ8x16 | 16 | 32 | L2 |26438401 | 2199527 |26280149 | 2143973 | -2.53% | -0.60% | Δ_PQ%: PQ baseline -> RVV; Δ_F%: Flat baseline -> RVV. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5543 Test Plan: `buck build fbcode//faiss:faiss` passes. `buck2 test` passes on the PQ and the distance C++ tests: `test_disable_pq_sdc_tables`, `test_distances_dispatch`, `test_distances_simd`, `test_ivfpq_codec`, `test_ivfpq_indexing`, `test_pq_encoding` and `test_pq_code_distance`. The result is 27 pass and 0 fail. The host is aarch64, so 8 tests skip. Those tests need a second SIMD level to compare against. This diff adds 2 tests to `faiss/tests/test_product_quantizer.py`: - `test_dsub2_4bit` covers `dsub=2` with `nbits=4`. `ksub` is 16, so the SIMD `dsub2` kernel runs. - `test_dsub2_2bit` covers `dsub=2` with `nbits=2`. `ksub` is 4, so the generic path must run instead. I checked the `nbits >= 3` fix with a temporary C++ test on ARM NEON. The test compares `compute_distance_tables` and `compute_inner_prod_tables` against `compute_distance_table` and `compute_inner_prod_table`, for `nbits` of 1, 2, 3 and 4. The test fails with a `ksub % 8 == 0` assertion before the fix. The test passes after the fix. I removed the temporary test before submit. Limits of the local verification: - I did not run `faiss/tests/test_product_quantizer.py` on this devserver. The `fbcode//faiss/python:pyfaiss-py-gen` SWIG step fails on aarch64 with `Exec format error`. The failure also reproduces without my changes. CI runs the Python tests on x86. - I did not compile `utils/simd_impl/distances_rvv.cpp`. This devserver has no RISC-V toolchain. `xplat.bzl` registers no RVV sources, so Buck and internal CI do not build that file either. Only the OSS CMake build on rv64 compiles it. A reviewer with RVV hardware should confirm the 4 RVV kernel fixes. Reviewed By: juancarpio27 Differential Revision: D117914440 Pulled By: mnorris11 fbshipit-source-id: 3539a116d47f4a96c1051bc10e6440deae8c5302	2026-09-24 18:31:50 -07:00
4 people	f323c18d5a	Add RVV encoding for QT_8bit_direct (#5640) ... Summary: RVV `QT_8bit_direct` currently inherits scalar encoding. This adds an RVV encoder using `e32m4`, explicit round-toward-zero float-to-unsigned conversion, and two narrowing operations before storing bytes. The generic encoder becomes overridable so the RVV specialization can provide the implementation. The portable scalar conversion domain is finite inputs in `(-1, 256)`, whose truncated values are representable in `uint8_t`; negative fractions greater than -1 produce zero. The new regression test covers that domain, including signed zero, subnormals, values around integer boundaries, the largest float below 256, short tails, and output guards. This PR is independent of the FP16 and direct-signed-distance changes. ### Performance Measured on a native SG2044 RISC-V host (VLEN=128), GCC 15.1, Release `-O3`, dynamic dispatch (`FAISS_OPT_LEVEL=dd`), `rv64gcv_zvfhmin/lp64d`, one thread pinned to CPU 2. The baseline is official commit `80a16564f86530dbf0bfaf96c2b71feffeb5093f`; the candidate is that same baseline plus only this kernel change. These measurements were not collected on the newer PR base `2ed4c106e9fb9686e7727e5daf8ad6ad1e164109`. The affected scalar-quantizer source files are unchanged between those bases, and the submitted kernel differs from the measured one only in comments/formatting. | Public path | Dimension | Baseline ns/element | Candidate ns/element | Paired speedup | 95% interval | |---|---:|---:|---:|---:|---:| | Direct-u8 encode | 16 | 1.839 | 1.345 | 1.366x | [1.343, 1.379] | | Direct-u8 encode | 32 | 1.839 | 1.061 | 1.750x | [1.690, 1.775] | | Direct-u8 encode | 128 | 1.640 | 0.823 | 1.937x | [1.901, 1.992] | | Direct-u8 encode | 768 | 1.530 | 0.740 | 2.059x | [1.883, 2.105] | Geometric mean of the dimension-specific speedups at d=32/128/768: Direct-u8 encode **1.911x**. There are three consecutive sessions, each with four alternating ABBA/BAAB blocks per dimension/path: **48 paired blocks** for this candidate. A is the baseline and B is the candidate. Each call is calibrated to at least 0.1 s (the shortest formal call in the full campaign was 0.192 s), with three warm-up batches and `n = max(32, floor(32768/d))`. Each block uses the ratio of the two-call geometric mean times. Reported speedup is the median of the three session medians; intervals use 5,000 hierarchical bootstrap resamples, resampling sessions and then blocks within each ABBA/BAAB order stratum. The timing columns are separate medians, so their quotient need not equal the paired speedup. All 48 paired blocks favored this candidate. The timed operation is public `ScalarQuantizer::compute_codes`, using fixed-seed (718) finite input batches. Direct-u8 input values are `float(rng()%16777216)/65536.f`. These results describe public encoding/distance throughput on one non-exclusive host, not end-to-end ANN search speedup. The intervals describe these sessions only, with no multiple-comparison correction; they do not establish portability across machines or vector lengths. ### Validation - Native public encoding oracle: **7,724,670** legal-domain input elements across the five RISC-V rounding modes; zero differing output bytes or write-guard failures. Inputs include negative fractions, signed zeros, subnormals, all byte-value boundaries, and values just below 256. - Original benchmark baseline full C++ suite: **273 passed, 7 skipped, 0 failed**. - Submission version on `2ed4c106e9fb9686e7727e5daf8ad6ad1e164109`: all three independent candidate builds succeeded; this PR's focused C++ suite (`NONE`: 11 passed, 5 skipped, 0 failed; `RISCV_RVV`: 12 passed, 4 skipped, 0 failed) and the public-path oracle above pass on native RISC-V. The newly added RVV regression test is executed and passed in the RVV run, and skipped when RVV is disabled in the NONE run. - All touched C++ files pass clang-format 21.1.8; `git diff --check` clean. ### Notes - Touches three files: `faiss/impl/scalar_quantizer/quantizers.h` (one-line `final` → `override` so the generic encoder can be specialized), `faiss/impl/scalar_quantizer/sq-rvv.cpp` (the RVV encoder), and `tests/test_scalar_quantizer.cpp` (one regression test). - The conversion uses `vfcvt.rtz.xu.f.v` (round toward zero, float to unsigned) rather than a signed conversion. The generic encoder is `code[i] = (uint8_t)x[i]`, which is a C++ float-to-unsigned-integral truncation, so round-toward-zero is the matching mode. Negative fractions greater than -1 truncate to 0 in both paths. - Two narrowing shifts (`vnsrl` by 0) are used to go `u32m4 → u16m2 → u8m1` before the byte store, avoiding a separate saturating narrow instruction. - The kernel is VLEN-agnostic: `e32m4` lanes with `vsetvl`-driven loop bounds. At VLEN=128 this processes 16 elements per iteration. - Quantization is not clamped. Inputs outside `(-1, 256)` are outside the portable domain — the scalar path casts out-of-range floats to `uint8_t`, which is undefined behavior for values outside that range, so no portable contract exists to preserve there. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5640 Reviewed By: trang-nm-nguyen Differential Revision: D121445607 Pulled By: mnorris11 fbshipit-source-id: 16f34cf77aa0cac2fd99ccb245f2ffbc2047d6c4 Co-authored-by: ihb2032 <[email protected]> Co-authored-by: lyd1992 <[email protected]> Co-authored-by: Yuansheng <[email protected]>	2026-09-24 12:35:28 -07:00
Lucian Grijincu	2496f63f76	Avoid search stats contention during concurrent search (#5663) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5663 Follow-up to D121097648 (public PR: https://github.com/facebookresearch/faiss/pull/5657). Related public PR: https://github.com/facebookresearch/faiss/pull/4910 Use relaxed atomic additions for HNSW, RaBitQ, and IVFPQ stats aggregation. Builds with `std::atomic_ref` support use `fetch_add(..., std::memory_order_relaxed)`; older standard libraries fall back to `__atomic_fetch_add(..., __ATOMIC_RELAXED)`. This removes the global OpenMP critical sections that serialize concurrent searches while preserving exact counter updates. Benchmark design: mode/opt `bench_hnsw_stats` binary, one shared HNSW index, `N` external pthreads, one OpenMP thread per search (each worker calls `omp_set_num_threads(1)` once before its timed loop), five repetitions per point. Performance: | External pthreads | Critical M/s | Relaxed atomic M/s | Speedup | |---:|---:|---:|---:| | 1 | 2.228 | 2.503 | 1.12x | | 2 | 3.716 | 3.853 | 1.04x | | 4 | 5.662 | 7.357 | 1.30x | | 8 | 6.384 | 12.843 | 2.01x | | 16 | 2.697 | 15.804 | 5.86x | | 32 | 0.951 | 18.910 | 19.88x | | 64 | 0.117 | 21.866 | 186.89x | At 64 pthreads, the feature-detected `atomic_ref` path measured 21.918 M/s mean over 10 repetitions (21.907 M/s median, 2.59% CV). The `__atomic_fetch_add` fallback measured 22.563 M/s mean (22.511 M/s median, 3.24% CV). The 64-thread profile attributes 97.38% of cycles in the critical-section version to lock acquisition and waiting. With relaxed atomic aggregation, 74.14% is in the stats combine path instead. The remaining non-linear scaling, 21.866 M/s at 64 threads versus the 2.503 M/s single-thread baseline, comes from cache-line contention on the global counters and shared-index memory-bandwidth and cache pressure. Reviewed By: mnorris11 Differential Revision: D121368933 fbshipit-source-id: 8dd26313e55aa73c0cdd379c7648efacd4f5f1d8	2026-09-23 19:27:47 -07:00
ihb2032	5e74b1bdde	feat: implement RVV optimized scalar quantizer codecs and distance computation (#5535) ... Summary: This PR adds RISC-V Vector Extension SIMD support for Faiss scalar quantizer. The implementation introduces runtime vector-length aware RVV kernels using the m8 vector configuration, instead of assuming a fixed vector width. This matches the variable-length nature of RVV hardware and allows the implementation to scale across different RISC-V vector implementations. ## Changes - Add RVV implementations for scalar quantizer codecs: - 8-bit codec decoding - 4-bit codec decoding - (6-bit stays scalar: the RVV gather decoder measured 12-22% slower than the scalar path, so QT_6bit falls back until a faster decoder exists) - Add RVV quantizer reconstruction support for: - Uniform quantizers - Non-uniform quantizers - FP16 (Zvfhmin is the enforced minimum ISA of the RISCV_RVV level; a build without it fails compilation rather than silently falling back) - BF16 - Direct 8-bit quantization - Signed 8-bit quantization - LloydMax quantizers (1/2/3/4/8-bit) - Add RVV optimized similarity implementations: - L2 distance - Inner product Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5535 Reviewed By: mnorris11 Differential Revision: D116996553 Pulled By: juancarpio27 fbshipit-source-id: dc726948fa602a04a757d8f9cab8eea41ac1979a	2026-09-23 12:00:59 -07:00
Mulugeta Mammo	b0d9e80288	Add fast scan variants of SQ indexes - IndexSQFastScan and IndexIVFSQFastScan (#5341) ... Summary: This PR introduces `IndexSQFastScan` and `IndexIVFSQFastScan`, fast scan variants of scalar quantized indexes. **IndexSQFastScan** (33f2cb639bd7a888b2ab7578083b73753c2fd3d3) Introduces `IndexSQFastScan`, a fast scan variant of `IndexScalarQuantizer` that leverages the PQ4 FastScan SIMD infrastructure (`vpshufb`) for accelerated search over scalar-quantized codes. Three code paths depending on quantizer type: - Native 4-bit (`QT_4bit`, `QT_4bit_uniform`): codes map directly onto the 16-level PQ4 fast scan. ~11x speedup, no precision loss. - Rerank (`QT_6bit`, `QT_8bit`, `QT_8bit_uniform`, `QT_8bit_direct`, `QT_8bit_direct_signed`): re-quantize to 4-bit for a coarse fast scan first pass, then rerank top-k*rerank_factor candidates with exact original-precision distances. ~7-9x speedup, near-zero precision loss at rerank_factor=4. - Fallback (`QT_fp16`, `QT_bf16`, `TurboQuant`, etc.): delegates to the ScalarQuantizer's own SIMD-optimized scanner. Same speed as IndexScalarQuantizer — no fast scan benefit, but provides a unified interface for all quantizer types. **benchmark**: `benchs/bench_index_sq_fastscan.py` ```text +---------------------+----------------------+---------+---------+--------+--------+ | Category | QType | Speedup | ms/q SQ | R@1 | R@10 | +---------------------+----------------------+---------+---------+--------+--------+ | Native 4-bit (SIMD) | QT_4bit | 11.9x | 0.240 | 0.7714 | 0.9985 | | | QT_4bit_uniform | 11.7x | 0.235 | 0.7180 | 0.9952 | +---------------------+----------------------+----------+---------+--------+--------+ | Rerank (rf=4) | QT_6bit | 9.3x | 0.202 | 0.9371 | 1.0000 | | | QT_8bit | 8.4x | 0.173 | 0.9783 | 1.0000 | | | QT_8bit_uniform | 6.7x | 0.138 | 0.9728 | 1.0000 | | | QT_8bit_direct | 4.7x | 0.101 | 0.9914 | 1.0000 | | | QT_8bit_direct_signed| 4.9x | 0.101 | 0.5999 | 0.6591 | +---------------------+----------------------+----------+---------+--------+--------+ | Fallback (~1.0x) | QT_fp16 | 0.9x | 0.373 | 0.9914 | 1.0000 | | | QT_bf16 | 1.0x | 0.365 | 0.9914 | 1.0000 | | | QT_8bit_tqmse | 1.0x | 0.261 | 0.6033 | 0.9561 | | | QT_5bit_tq | 1.0x | 3.013 | 0.2680 | 0.6248 | | | QT_4bit_tq | 1.0x | 2.416 | 0.1511 | 0.3994 | | | QT_3bit_tq | 1.0x | 0.411 | 0.0487 | 0.1691 | | | QT_2bit_tq | 1.1x | 0.231 | 0.0376 | 0.1532 | | | QT_4bit_tqmse | 1.0x | 0.290 | 0.0012 | 0.0064 | | | QT_3bit_tqmse | 1.0x | 0.345 | 0.0000 | 0.0001 | | | QT_2bit_tqmse | 1.0x | 0.266 | 0.0000 | 0.0001 | | | QT_1bit_tqmse | 1.0x | 0.280 | 0.0000 | 0.0001 | +---------------------+----------------------+----------+---------+--------+--------+ Key: Speedup = IndexScalarQuantizer ms / IndexSQFastScan ms R@1, R@10 = IndexSQFastScan recall (matches SQ for all fallback types) Rerank shows rf=4 (rf=2 and rf=8 yield same recall, ~0.1x speedup variation) Dataset: SIFT1M, k=32 ``` **IndexIVFSQFastScan** (ebfa072816df2fbd80a6b463a913866f862587f6) Similar to the above, this commit introduces `IndexIVFSQFastScan`, an IVF variant of scalar quantized fast scan that extends the PQ4 FastScan SIMD infrastructure (vpshufb) to inverted-list indexes with scalar quantization. Uses BlockInvertedLists for packed 4-bit codes scanned via SIMD. Will continue to update the PR until it's feature complete. Three code paths depending on quantizer type: - Native 4-bit (QT_4bit, QT_4bit_uniform): codes pack directly into the SIMD block layout with no precision loss. ~12x speedup. - Rerank (QT_6bit, QT_8bit, QT_8bit_uniform, QT_8bit_direct, QT_8bit_direct_signed): re-quantized to 4-bit for the SIMD coarse pass, then reranked using exact original-precision codes stored in a parallel ArrayInvertedLists. ~8-10x speedup, near-zero precision loss at rerank_factor=2. - Fallback (QT_fp16, QT_bf16, TurboQuant, etc.): delegates to IndexIVF's InvertedListScanner path. Same behavior as IndexIVFScalarQuantizer — no fast scan benefit, but provides a unified interface for all quantizer types. **benchmark (SIFT1M, d=128, k=32, SapphireRapids)**: `benchs/bench_index_ivf_sq_fastscan.py` ```text +---------------------+----------------------+--------+-------------------------------------------+ | Category | QType | nprobe | Speedup | ms/q SQ | R@1 FS | R@10 FS | +---------------------+----------------------+--------+---------+---------+--------+-------------+ | Native 4-bit (SIMD) | QT_4bit | 1 | 7.1x | 0.007 | 0.4582 | 0.5456 | | | | 4 | 10.4x | 0.007 | 0.6903 | 0.8667 | | | | 16 | 12.9x | 0.022 | 0.7668 | 0.9885 | | | | 64 | 12.1x | 0.070 | 0.7725 | 0.9983 | | | | 256 | 11.3x | 0.230 | 0.7725 | 0.9983 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_4bit_uniform | 1 | 15.8x | 0.006 | 0.4397 | 0.5449 | | | | 4 | 10.5x | 0.007 | 0.6419 | 0.8650 | | | | 16 | 10.4x | 0.018 | 0.7113 | 0.9855 | | | | 64 | 10.9x | 0.063 | 0.7162 | 0.9951 | | | | 256 | 11.0x | 0.222 | 0.7162 | 0.9951 | +---------------------+----------------------+--------+---------+---------+--------+-------------+ | Rerank (rf=4) | QT_6bit | 1 | 4.9x | 0.007 | 0.4582 | 0.5456 | | | | 4 | 4.8x | 0.007 | 0.6903 | 0.8667 | | | | 16 | 7.9x | 0.018 | 0.7668 | 0.9885 | | | | 64 | 10.4x | 0.067 | 0.7725 | 0.9983 | | | | 256 | 10.2x | 0.221 | 0.7725 | 0.9983 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_8bit | 1 | 17.1x | 0.007 | 0.4582 | 0.5456 | | | | 4 | 12.5x | 0.008 | 0.6903 | 0.8667 | | | | 16 | 8.9x | 0.015 | 0.7668 | 0.9885 | | | | 64 | 8.4x | 0.049 | 0.7725 | 0.9983 | | | | 256 | 9.3x | 0.188 | 0.7725 | 0.9983 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_8bit_uniform | 1 | 18.2x | 0.007 | 0.4397 | 0.5449 | | | | 4 | 11.1x | 0.008 | 0.6419 | 0.8650 | | | | 16 | 8.3x | 0.014 | 0.7113 | 0.9855 | | | | 64 | 7.8x | 0.045 | 0.7162 | 0.9951 | | | | 256 | 7.8x | 0.164 | 0.7162 | 0.9951 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_8bit_direct | 1 | 8.6x | 0.007 | 0.4083 | 0.5426 | | | | 4 | 7.0x | 0.008 | 0.5987 | 0.8587 | | | | 16 | 6.8x | 0.013 | 0.6550 | 0.9756 | | | | 64 | 6.1x | 0.035 | 0.6581 | 0.9850 | | | | 256 | 7.4x | 0.150 | 0.6581 | 0.9850 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_8bit_direct_signed| 1 | 16.5x | 0.006 | 0.4257 | 0.5447 | | | | 4 | 10.1x | 0.007 | 0.6286 | 0.8633 | | | | 16 | 7.1x | 0.012 | 0.6919 | 0.9831 | | | | 64 | 5.7x | 0.033 | 0.6963 | 0.9923 | | | | 256 | 7.1x | 0.145 | 0.6963 | 0.9923 | +---------------------+----------------------+--------+---------+---------+--------+-------------+ | Fallback (~1.0x) | QT_fp16 | 1 | 1.0x | 0.007 | 0.5434 | 0.5462 | | | | 4 | 1.1x | 0.013 | 0.8607 | 0.8678 | | | | 16 | 0.9x | 0.035 | 0.9814 | 0.9902 | | | | 64 | 0.9x | 0.115 | 0.9912 | 1.0000 | | | | 256 | 0.9x | 0.481 | 0.9912 | 1.0000 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_bf16 | 1 | 1.0x | 0.008 | 0.5427 | 0.5462 | | | | 4 | 1.1x | 0.013 | 0.8581 | 0.8678 | | | | 16 | 1.0x | 0.035 | 0.9778 | 0.9902 | | | | 64 | 1.0x | 0.115 | 0.9876 | 1.0000 | | | | 256 | 1.0x | 0.487 | 0.9876 | 1.0000 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_5bit_tq | 1 | 1.0x | 0.016 | 0.1866 | 0.3827 | | | | 64 | 1.0x | 0.794 | 0.2680 | 0.6248 | | | | 256 | 1.0x | 2.885 | 0.2680 | 0.6248 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_4bit_tq | 1 | 1.0x | 0.013 | 0.1182 | 0.2841 | | | | 64 | 0.9x | 0.618 | 0.1511 | 0.3994 | | | | 256 | 0.9x | 2.298 | 0.1511 | 0.3994 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_3bit_tq | 1 | 1.1x | 0.008 | 0.0526 | 0.1599 | | | | 64 | 0.8x | 0.092 | 0.0488 | 0.1696 | | | | 256 | 0.8x | 0.357 | 0.0487 | 0.1691 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_2bit_tq | 1 | 1.2x | 0.008 | 0.0450 | 0.1526 | | | | 64 | 1.1x | 0.072 | 0.0377 | 0.1534 | | | | 256 | 1.1x | 0.224 | 0.0376 | 0.1532 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_4bit_tqmse | 1 | 1.0x | 0.007 | 0.0619 | 0.1851 | | | | 64 | 1.0x | 0.072 | 0.0002 | 0.0010 | | | | 256 | 0.9x | 0.275 | 0.0000 | 0.0000 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_3bit_tqmse | 1 | 1.0x | 0.007 | 0.0621 | 0.1852 | | | | 64 | 1.0x | 0.090 | 0.0006 | 0.0032 | | | | 256 | 1.0x | 0.350 | 0.0000 | 0.0000 | | +----------------------+--------+---------+---------+--------+-------------+ | | QT_2bit_tqmse | 1 | 1.1x | 0.007 | 0.0621 | 0.1852 | | | | 64 | 1.0x | 0.068 | 0.0015 | 0.0080 | | | | 256 | 1.0x | 0.244 | 0.0000 | 0.0000 | +---------------------+----------------------+--------+---------+---------+--------+-------------+ Key: Speedup = IndexIVFScalarQuantizer ms / IndexIVFSQFastScan ms R@1, R@10 = IVFSQFastScan recall (matches IVF-SQ for all fallback types) Rerank shows rf=4 only (rf=2,8 yield similar results) Fallback shows nprobe=1,64,256 only (abbreviated for low-recall types) Dataset: SIFT1M, nlist=256, k=32 ``` Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5341 Reviewed By: junjieqi Differential Revision: D117259284 Pulled By: mnorris11 fbshipit-source-id: 41455097ff3ae1285aeb4cf88e07abc5b5b13171	2026-09-18 20:24:54 -07:00
Mihai Capotă	4864f4d420	SVS: Add ParameterSpace.set_index_parameter support for Vamana (#5644) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5644 Reviewed By: alibeklfc Differential Revision: D120290334 Pulled By: mnorris11 fbshipit-source-id: c947484d0704789553a7d4d80a0ef7185e59962a	2026-09-18 10:15:10 -07:00
郑紫阳10295048	0f23e6a2ef	Add RVV SIMD specialization for scalar quantizer distance compute (#5539) ... Summary: This PR adds RISC-V Vector Extension SIMD specialization for the scalar quantizer distance computation, following the codec/quantizer/similarity specialization already present for other SIMD levels. The kernels use the runtime vector-length aware m8 vector configuration and are shared across all RVV hardware widths, instead of assuming a fixed vector length. Changes Add RVV specialized L2 / inner-product distance kernels for the scalar quantizer codecs: - QT_4bit / QT_4bit_uniform - QT_6bit - QT_8bit / QT_8bit_uniform - QT_8bit_direct / QT_8bit_direct_signed - QT_bf16 - QT_fp16 Each kernel reuses the reconstructed (quantizer) L2 / IP formulation that avoids per-dimension reconstruction, keeping the hot loop in the integer domain and applying the final scale at the tail. Performance Cmd: 1M 768 <SQ> 32 100 16 1 1000 1 <metric> (search ms/query, lower is better) Δ_SQ%: SQ scalar baseline -> RVV; Δ_F%: Faiss flat baseline -> RVV. | 序号 | QT_TYPE | Metric | F1(ms) | SQ1(ms) | F2(ms) | SQ2(ms) | Δ_SQ% | Δ_F% | |------|-----------------------|--------|--------|---------|--------|---------|---------|--------| | 01 | QT_4bit | L2 | 1.841 | 6.231 | 1.824 | 1.450 | -76.73% | -0.92% | | 02 | QT_4bit | IP | 1.652 | 6.086 | 1.674 | 1.273 | -79.08% | +1.33% | | 03 | QT_4bit_uniform | L2 | 1.806 | 2.560 | 1.806 | 1.135 | -55.66% | +0.00% | | 04 | QT_4bit_uniform | IP | 1.612 | 6.007 | 1.597 | 1.244 | -79.29% | -0.93% | | 05 | QT_6bit | L2 | 1.801 | 5.701 | 1.805 | 1.500 | -73.69% | +0.22% | | 06 | QT_6bit | IP | 1.608 | 5.706 | 1.619 | 1.249 | -78.11% | +0.68% | | 07 | QT_8bit | L2 | 1.821 | 3.736 | 1.907 | 1.394 | -62.69% | +4.72% | | 08 | QT_8bit | IP | 1.704 | 3.378 | 1.730 | 1.277 | -62.20% | +1.53% | | 09 | QT_8bit_direct | L2 | 1.977 | 0.280 | 1.947 | 0.054 | -80.71% | -1.52% | | 10 | QT_8bit_direct | IP | 1.709 | 0.458 | 1.740 | 0.099 | -78.38% | +1.81% | | 11 | QT_8bit_direct_signed | L2 | 1.581 | 3.234 | 1.572 | 0.761 | -76.47% | -0.57% | | 12 | QT_8bit_direct_signed | IP | 1.740 | 0.414 | 1.748 | 0.148 | -64.25% | +0.46% | | 13 | QT_8bit_uniform | L2 | 1.943 | 3.204 | 1.928 | 0.927 | -71.07% | -0.77% | | 14 | QT_8bit_uniform | IP | 1.727 | 3.121 | 1.744 | 0.947 | -69.66% | +0.98% | | 15 | QT_bf16 | L2 | 1.862 | 2.889 | 1.894 | 1.466 | -49.26% | +1.72% | | 16 | QT_bf16 | IP | 1.619 | 2.846 | 1.793 | 1.204 | -57.70% | +10.75% | | 17 | QT_fp16 | L2 | 2.011 | 5.691 | 1.950 | 1.570 | -72.41% | -3.03% | | 18 | QT_fp16 | IP | 1.797 | 5.584 | 1.790 | 1.189 | -78.71% | -0.39% | Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5539 Reviewed By: mnorris11 Differential Revision: D117914328 Pulled By: juancarpio27 fbshipit-source-id: 879863b9ab4da6d1c8685892ccc3d64190975181	2026-09-17 13:34:43 -07:00
YingzuoLiu	3778f5892d	Fix IDSelector handling in unbounded HNSW search (#5508) ... Summary: - apply `SearchParametersHNSW.sel` to the unbounded HNSW search path - keep filtered nodes available for graph traversal while excluding them from the result set - add regression coverage for L2 and inner-product search, restrictive `efSearch`, and an empty selector ## Root cause The bounded HNSW path applies the selector through its result handler. The unbounded path did not receive the selector and used the same heap for traversal pruning and final results, so IDs rejected by `SearchParameters.sel` could be returned. ## Implementation When a selector is present, the unbounded path maintains a separate result heap containing only accepted IDs. The existing candidate heap remains unchanged and can still contain rejected nodes, preserving traversal through them. When no selector is present, the existing unfiltered result behavior is preserved. ## Validation - issue reproducer: unbounded search now returns ID 1 at distance 100.0 instead of rejected ID 0 - `tests/test_search_params.py`: 52 passed - HNSW C++ tests: 14 passed - full CPU C++ test suite: 278 passed, 5 skipped - clang-format and `git diff --check`: passed Fixes https://github.com/facebookresearch/faiss/issues/5504 Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5508 Reviewed By: alibeklfc Differential Revision: D120364656 Pulled By: mnorris11 fbshipit-source-id: 074234b80cf7b2e06a85d57489a1c214dfd3195b	2026-09-16 17:55:51 -07:00
Jaeyoon Jeong	3b3711c112	Add explicit IVFPQ scanner distance modes (#5632) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5632 Add an explicit IVFPQ scanner mode that preserves precomputed-table behavior by default and can decode PQ codes to compute residual L2 distances on demand. Keep the existing scanner factory overload compatible. Reviewed By: mdouze Differential Revision: D119608525 fbshipit-source-id: b60b2c9771bdfd95d9bee2e81b72c9c3e7abb82c	2026-09-15 17:32:23 -07:00
Alibek Zhakubayev	3bb48643ab	Pin faiss-gpu-cuvs RAPIDS deps to the 26.06 build series (#5643) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5643 `faiss-gpu-cuvs` 1.15.0 fails at import on a clean install: ``` ImportError: libfaiss.so: undefined symbol: _ZTIN3rmm9bad_allocE ``` ## Root cause, measured RAPIDS 26.08 wrapped RMM in a per-release ABI inline namespace. `nm -D` on the published `librmm-cu13` wheels: | Version | `typeinfo for rmm::bad_alloc` | Exported instead | | --- | --- | --- | | 26.2.0 | present | | | 26.4.0 | present | | | 26.6.0 | present | | | 26.8.0 | **absent** | `typeinfo for rmm::_RMM_26_8::bad_alloc` | `pyproject-gpu-cuvs.toml` builds against `==26.06.*` in `before-all` but declares `>=26.06,<27` at runtime and in `test-requires`. A fresh install therefore pairs a 26.06-built `libfaiss.so` with a 26.8 `librmm.so` that renamed every `rmm::` symbol. Nothing vendored covers the gap: `repair-wheel-command` hands every RAPIDS `lib*.so*` under `/opt/cuvs` to `auditwheel --exclude`. The 1.15.0 wheel was uploaded 2026-08-03, two days before RAPIDS 26.08 reached PyPI. It published green and began failing for every new installer afterwards, which matches `build-pip-gpu / Build & test faiss-gpu-cuvs` going red on 2026-08-05 after 68 consecutive passes. An exact-series pin rather than a narrower range is required: the inline namespace encodes the release, so **any** range spanning more than one RAPIDS minor series is broken by construction. ## This diff - Pin `libcuvs-cu13`, `libraft-cu13`, and `librmm-cu13` to `==26.06.*` in both `dependencies` and `test-requires`. - Declare `libraft-cu13`. `faiss/python/__init__.py` imports `libraft` and calls `libraft.load_library()`, but only `before-all` installed it, so at runtime its version floated on `libcuvs-cu13` transitive metadata. - Correct the cuSOLVER soname in the `auditwheel` exclude list from `libcusolver.so.11` to `libcusolver.so.12`, which is what CUDA 13.2 ships. - Update the `_preload_gpu_libs` fix-it message, which told users to install the range this diff removes. - Add `TestCuvsRapidsPinning` to `tests/test_wheel_smoke_gpu.py`. ## Regression guard `tests/test_wheel_smoke_gpu.py` is already the `test-command` for the cuVS wheel, so the new class runs inside `build-pip-gpu.yml` with no workflow change and no new test file. It asserts three properties of the built wheel's own `Requires-Dist`: 1. every RAPIDS distribution `_preload_gpu_libs` dlopens is declared 2. each is pinned to `==26.06.*` rather than an open range 3. the installed versions sit in that series `_RAPIDS_SERIES` duplicates the series from `pyproject-gpu-cuvs.toml` because the wheel does not ship that file. The duplication is the tripwire: a RAPIDS bump has to touch both places deliberately. ## Prior attempt D117099095 made the version-pin change on 2026-08-23 and was abandoned on 2026-09-04 without landing. It never failed review. `faiss/public_tld/` is ShipIt-mirrored with `requireExportConfig`, so `github-export-checks` held it Unpublished pending a `facebookresearch/faiss` PR that a bot cannot open, and three pings over 12 days went unanswered. This diff needs that same export. ## Notes The published 1.15.0 metadata declares only `libcuvs-cu13`, not `librmm-cu13`. That is not a fbsource/GitHub divergence: `librmm-cu13` was added to `dependencies` on 2026-08-14, after the 08-03 release, and has never shipped. `rapids-logger` is installed by `before-all` but stays undeclared here. `librmm-cu13` owns that link-time dependency and carries it in its own metadata; an unversioned duplicate would not make the resolve safer. Reviewed By: mnorris11 Differential Revision: D120162004 fbshipit-source-id: eb6dc316a4fba2a4228eab62d7b86ac8ea94a1b7	2026-09-15 14:42:20 -07:00
Trang Nguyen	7c3b55c01b	Make Panorama bounds checks overflow-safe (#5616) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5616 Follow up on D118495504 by closing two arithmetic gaps in the Panorama bounds validation. Avoid signed overflow and reject negative counts in `IndexFlatPanorama::reconstruct_n`, and compute the serialized `IndexFlatPanorama` batch count without overflowing `ntotal + batch_size - 1`. Add regression coverage for negative reconstruction counts and a maximal serialized batch size that previously admitted empty storage for a non-empty index. Reviewed By: mnorris11 Differential Revision: D119272683 fbshipit-source-id: 7ea841bd4bd90d0358b78797441fa3cc815db46a	2026-09-14 21:26:48 -07:00
Trang Nguyen	fb2d57a312	Fix leak and unbounded lists[] in OnDisk invlist deserialization (#5560) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5560 `OnDiskInvertedListsIOHook::read` allocates its `OnDiskInvertedLists` with a bare `new` and then keeps reading. Any throw after that point leaks the whole object -- including `od->lists`, which `READVECTOR` will happily size up to `get_deserialization_vector_byte_limit()`. Throwing after that point is the common case for malformed input: the `slots` and `filename` reads can fail, and `do_mmap()` on an attacker-controlled filename fails essentially always. This is what the `faiss_read_index_binary_fuzzer` health check has been tripping over. The one CI stack that survived tpx truncation names `OnDiskInvertedLists.cpp:722` (`vector<OnDiskOneList>::resize`) as the largest live allocation, reached via `IBFf` -> `read_index` -> `IxRP` -> IVF -> `read_InvertedLists`. Because the harness runs with `detect_leaks: 0`, the leaked blocks accumulate across a 120 s session; peak RSS across the failing runs climbed 978 -> 1142 -> 1249 -> 1815 -> 4356 MB against `-rss_limit_mb=4096`. That is why the check reads as flaky (23.6%) rather than as a hard red, and why the saved crash artifacts do not reproduce when replayed one at a time. Switch both `read` and `read_ArrayInvertedLists` to hold the object in a `std::unique_ptr` and `release()` on success. The public signature still returns `InvertedLists*`, so this is a local scope guard only -- the same shape `read_InvertedLists_up` in `index_read.cpp` already uses. Also reject `lists.size() != nlist` at read time. Every `OnDiskInvertedLists` accessor (`list_size`, `get_codes`, `get_ids`, ...) indexes `lists[list_no]` with `list_no` bounded only against `nlist`, so a file whose `lists` vector is shorter than its `nlist` is a straight out-of-bounds read. Every construction path in the class keeps `lists.size() == nlist`, so this rejects only malformed input. Reviewed By: mnorris11 Differential Revision: D118487565 fbshipit-source-id: 6f01c937b24a2a98620e4ca2bde141674af1b19d	2026-09-14 21:23:31 -07:00
Michael Norris	a74867cf56	faiss HNSW: delete the flag and the lock-based graph build (#5611) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5611 D112025877 added the `faiss::hnsw_deterministic_build` flag. The flag chose between the lock-based graph build and the deterministic graph build. This diff deletes the flag. The deterministic build is now the only build. Reviewed By: trang-nm-nguyen Differential Revision: D118342471 fbshipit-source-id: d3c5e5238aca2bcda463eb27959ec22827222c15	2026-09-14 13:13:11 -07:00
Ge Gao	4fdbc9dc18	Support ZeroCopyIOReader for IndexRaBitQ deserialization (#5629) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5629 `IndexRaBitQ` keeps its database in `codes`, a `MaybeOwnedVector<uint8_t>` inherited from `IndexFlatCodes`, but both read branches (`Ixrq` for single-bit and `Ixrr` for multi-bit) used the raw `READVECTOR` macro. So `codes` was always an owning heap vector even when the caller passed a view-capable reader, while every other flat-codes index already goes through `read_vector`. This switches both branches to `read_vector`, which dispatches on the reader type in `read_vector_base` and makes `codes` a view of the caller's buffer. Any other reader falls back to `READVECTOR`, so existing callers are unaffected. A zero-copy RaBitQ index now works like this: ``` #include <faiss/impl/zerocopy_io.h> faiss::ZeroCopyIOReader reader(buffer.data(), buffer.size()); std::unique_ptr<faiss::Index> index_zc(faiss::read_index(&reader)); ``` The buffer must outlive the index, as with any `faiss::ZeroCopyIOReader`. Reviewed By: mnorris11 Differential Revision: D119297402 fbshipit-source-id: 95c5ba050cb3a0636a0899efbe886616a7a8a2fd	2026-09-14 13:03:13 -07:00
Michael Norris	b5a14632a6	Run the eight SIMD kernel tests that no build executed (#5620) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5620 **TL;DR:** Eight SIMD kernel tests never ran, and two byte-domain kernels trust their caller. This change makes three fixes: 1. **Six tests never compiled.** `test_rabitq_simd.cpp` hides them behind `COMPILE_SIMD_*` macros that the faiss target does not export. 2. **Two tests skipped themselves in a static build.** `TestSQByteDirectAcrossSIMDLevels` needs `SIMDLevel::NONE` as a reference, and a static build does not report that level. 3. **The byte kernels never test their dimension requirement.** `DistanceComputerByte` and `DistanceComputerByteSigned` read 16 bytes per loop step. ## 1. Six tests never compiled `test_rabitq_simd.cpp` wraps two blocks in `#ifdef COMPILE_SIMD_AVX2` and `#ifdef COMPILE_SIMD_AVX512`. The faiss target sets those macros as `preprocessor_flags`, and it does not export them. A test translation unit never sees them. So the preprocessor deleted both blocks. The file holds nine tests and ran three. The AVX2 block loses its guard, because every x86 faiss build holds the AVX2 kernels. Its three tests also lose an `#ifdef FAISS_ENABLE_DD` around a runtime skip, which the same problem disabled. `is_simd_level_available()` reports the right answer in a static build too. The AVX512 block moves to a dynamic dispatch target. A static x86 build compiles the AVX2 kernels only, so the test fails to link there rather than skips. `test_rabitq_simd_vpopcnt.cpp` becomes `test_rabitq_simd_dd.cpp`, because it now holds every RaBitQ test that a static build cannot link. A new `test_rabitq_simd_util.h` holds the scalar reference that both files call. ## 2. Two tests skipped themselves in a static build `TestSQByteDirectAcrossSIMDLevels` measured the index a second time at `SIMDLevel::NONE`, then compared the two runs. A static build reports only the level it compiles, and omits `NONE`, so both tests skipped. The tests now compute the distances from the definition. The distances are integers, so the reference is exact. The tests check absolute values now, instead of the agreement of two faiss paths. ## 3. The byte kernels trust the caller `DistanceComputerByte` and `DistanceComputerByteSigned` read 16 bytes per loop step, so they require `d % 16 == 0`. `sq-dispatch.h` enforces that, and no other caller builds them. A caller that ignores the requirement reads up to 15 bytes past each code and returns a wrong distance. Each constructor now tests the requirement and throws. The AVX2 and the ARM_NEON specializations both get the test. Reviewed By: alibeklfc Differential Revision: D119545379 fbshipit-source-id: ddfdcc30d3662f469b2ec3dbb9d5b9f4dafa21aa	2026-09-10 20:05:56 -07:00
Michael Norris	6bbb068ad8	Measure 20-byte Hamming codes eight at a time (#5587) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5587 **TL;DR:** Adds a batched 20-byte Hamming kernel that measures eight codes per call, the only thing that helps the 160-bit width, worth 1.21x end to end. A 20-byte code has no vector kernel at any x86 SIMD level. `HammingComputer20` measures one distance with three scalar popcounts at every level, including `AVX512_VPOPCNT`, so a scan of 160-bit codes runs the same code everywhere. Vectorizing a single 20-byte distance does not help. A masked 256-bit load plus `vpopcntq` plus a horizontal reduction measures the same as the scalar body, because the reduction costs more than the three popcounts it replaces. Measuring several codes per call does help, because it amortizes that reduction. This adds `hamming_batch()` to `HammingComputer20` at `AVX512_VPOPCNT`, which measures eight codes at once: - Eight codes span 160 bytes. `_mm512_popcnt_epi8` gives a count per byte. - `_mm512_sad_epu8` sums each aligned 8-byte group. - A 20-byte code covers two whole groups plus half of a group it shares with its neighbour, so each code needs one scalar popcount for its half. `IVFBinaryScannerL2::scan_codes` and `IVFBinaryScannerL2::scan_codes_range` call `hamming_batch()` when the computer declares a `batch_size`, then measure the remaining codes one at a time. A computer without a `batch_size` keeps the existing loop, so no other code size changes. The scanner holds the tiled query, and the constructor rejects a code size that does not match the computer. A caller therefore cannot reach the batch kernel with a stride the kernel does not read. The byte-wise popcount needs `AVX512_BITALG`, which is a separate CPUID bit from `AVX512_VPOPCNTDQ`. This adds the flag to the `AVX512_VPOPCNT` level and requires both bits to select it. Every CPU that has VPOPCNTDQ also has BITALG, so no CPU loses the level. An alternative byte-wise popcount built from `vpshufb`, which needs neither bit and would run at the plain `AVX512` level, measures only 1.08x against 1.54x, so it is not worth the wider reach. Reviewed By: alibeklfc Differential Revision: D118971285 fbshipit-source-id: 5fd4637c972e5c55e2695b32b9b15fba8181a242	2026-09-10 09:32:36 -07:00
Michael Norris	3c7042f17a	Let the binary Hamming paths reach the VPOPCNT kernels ... Summary: **TL;DR:** Points `IndexBinaryIVF` at the VPOPCNT level and instantiates its scanner in the translation unit compiled with `-mavx512vpopcntdq`, worth 1.58x at 256-bit and 1.41x at 512-bit on Genoa. Two things kept the binary Hamming paths on scalar popcount, whatever the host. `IndexBinaryIVF` builds its scanner and runs its searches through `with_simd_level`, which uses the BASE level mask. That mask holds no `AVX512_VPOPCNT` bit, so on a host that reports that level the dispatch falls through to `AVX512`, where the wide computers use scalar popcount. Two build variants, `faiss_omp_mock` and `faiss_no_multithreading`, hardcoded dynamic dispatch off. They compiled the AVX2 kernels only, so a consumer of either variant could not use runtime dispatch at all, whatever the build setting said. This change: - Moves the three dispatch sites in `IndexBinaryIVF.cpp` to `with_simd_level_with_vpopcnt`. Below that level the dispatch falls through to `AVX512`, as before. - Instantiates `IndexBinaryIVF_impl.h` in `hamming_avx512_vpopcnt.cpp`. That is the one translation unit compiled with `-mavx512vpopcntdq`, which the VPOPCNT computers need. Without it the new dispatch has no symbol to call. The include must follow the computer specializations, so it is placed after them. - Lets both build variants honour the dynamic dispatch setting. `HammingComputer16` and `HammingComputer20` still inherit the scalar body at this level, so a 16-byte or 20-byte code gains nothing here. `IVFBinaryScannerL2::scan_codes` also reads the heap top into a local `bound` instead of loading `simi[0]` on every code. Only `scan_codes` writes `simi`, so it refreshes `bound` after each `heap_replace_top` and the two forms return the same results. The test plan measures it. Reviewed By: alibeklfc Differential Revision: D118874433 fbshipit-source-id: dc74294ecaf178919fdd713abc60c44bbaa80347	2026-09-10 09:32:36 -07:00
lyang24	e6bd1d252c	Add AVX512 VPOPCNT dynamic dispatch level (#5531) ... Summary: ## What Split the existing VPOPCNTDQ RaBitQ and Hamming kernels from the full Sapphire Rapids SIMD level. DD builds now expose an `AVX512_VPOPCNT` capability for CPUs such as Ice Lake and Zen 4. The fallback chain is: `AVX512_SPR -> AVX512_VPOPCNT -> AVX512 -> AVX2 -> NONE` The ordinary static AVX512 target remains unchanged and contains no VPOPCNT instructions. ## Why The VPOPCNT kernels only require baseline AVX-512 plus `AVX512_VPOPCNTDQ`. Tying them to the SPR level unnecessarily excluded CPUs that support VPOPCNTDQ but not AVX512-FP16, notably Zen 4. ## Changes made while importing Two changes were needed on top of the pull request. **Feature detection read the wrong CPUID leaf.** `AVX512_VPOPCNTDQ` and `AVX512_VNNI` were read from leaf 1 ECX. Both live in leaf 7 subleaf 0 ECX, at bits 14 and 11. Leaf 1 ECX holds unrelated bits at those positions, so the new level was never selected on any CPU. Measured on an AMD Genoa host before the fix: the level reported as unavailable and detection returned `AVX512`. After the fix the same host reports `AVX512_VPOPCNT`. **The build definitions outside CMake were not updated.** The pull request renames three files. The other build description still named the old paths and had no entry for the new level, so the library did not build. This adds the level constant, its compiler flags, its `COMPILE_SIMD_AVX512_VPOPCNT` define, and the renamed paths. **The new level was not registered in the compiled-level mask.** `compiled_simd_levels()` reports which levels a binary holds, and `FAISS_SIMD_LEVEL` walks down from the requested level until it finds one that is present. The new level had no entry, so the override always stepped past it to `AVX512` and printed that the level was not compiled in. This was reported by `test_dispatch_with_env_var` on the open-source dynamic-dispatch build. **The test helper inferred available levels from `/proc/cpuinfo`.** A CPU feature does not imply that a level is compiled into the build, so the helper listed a level the override then refused. It now asks `SIMDConfig::is_simd_level_available()`, which reports compiled and supported. That is a subset of compiled, so every level it returns is one the override accepts. The mask and helper names also follow the naming used in the parent diff, so `AVAILABLE_SIMD_LEVELS_BASE_WITH_VPOPCNT` and `with_simd_level_with_vpopcnt`. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5531 Test Plan: ``` buck2 test fbcode//mode/opt -c faiss.dynamic_dispatch=true \ fbcode//faiss/tests:test_simd_levels fbcode//faiss/tests:test_rabitq_simd ``` Result: all pass. The build failures the imported version reported are cleared. All three configurations build: ``` buck2 build fbcode//mode/dev fbcode//faiss:faiss fbcode//faiss:faiss_no_multithreading fbcode//faiss:faiss_omp_mock buck2 build fbcode//mode/opt -c faiss.dynamic_dispatch=true <same three targets> buck2 build fbcode//mode/dev -c fbcode.arch=aarch64 <same three targets> ``` Detection on an AMD Genoa host, which has AVX512_VPOPCNTDQ and AVX512_BF16 but not AVX512_FP16: | | before the CPUID fix | after | | --- | --- | --- | | detected level | `AVX512` | `AVX512_VPOPCNT` | | `AVX512_VPOPCNT` available | 0 | 1 | | `AVX512_SPR` available | 0 | 0 | Reviewed By: alibeklfc Differential Revision: D118969754 Pulled By: mnorris11 fbshipit-source-id: d1ca52b614829a3d4b322c9fecf0c004f2174dab	2026-09-10 09:32:36 -07:00
Michael Norris	fc13c81fb8	Stop aarch64 falling back to SIMDLevel::NONE in faiss dispatch (#5572) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5572 **TL;DR:** Stops aarch64 running scalar code where a NEON or SVE kernel exists, adds the two missing NEON byte-domain kernels, and fixes `FAISS_SIMD_LEVEL` falling all the way to `NONE` on an uncompiled level. On aarch64 several faiss dispatch paths ran scalar code, or ran an `ARM_NEON` kernel where an `ARM_SVE` kernel already existed. This change enforces the order SVE -> NEON -> NONE on an ARM host. It also adds the one kernel pair that was missing. T287037898 reported the scalar-quantizer half. On aarch64 `IndexScalarQuantizer` with `QT_8bit_direct` or `QT_8bit_direct_signed` saved memory but lost throughput. `Refine(SQ8)` has the same problem, because `IndexRefine::search` calls `refine_index->get_distance_computer()`. ## What each call site gets | Call site | Before | After | | --- | --- | --- | | `QT_8bit_direct` on aarch64 | float-domain `DCTemplate` | NEON `DistanceComputerByte` | | `QT_8bit_direct_signed` on aarch64 | float-domain `DCTemplate` | NEON `DistanceComputerByteSigned` (new) | | `IndexFlat` distance computers, SVE host | `ARM_NEON` | `ARM_SVE` | | `AdditiveQuantizer::compute_centroid_norms`, SVE host | `ARM_NEON` | `ARM_SVE` | | `SuperKMeans` `block_l2`, SVE host | `ARM_NEON` | `ARM_SVE` | | `pq_code_distance` wrappers, SVE host | `ARM_NEON` | `ARM_SVE` | | `with_VectorDistance`, SVE host | `ARM_NEON` | `ARM_SVE` | | `FAISS_SIMD_LEVEL=ARM_SVE`, build without SVE | `NONE` | nearest compiled level | ## Three causes, fixed separately **1. Two missing kernels.** `sq-neon.cpp` held a scalar `DistanceComputerByte<Sim, ARM_NEON>` that nothing could reach, and no `DistanceComputerByteSigned<Sim, ARM_NEON>` at all. Both are now real NEON kernels. L2 and the unsigned inner product use `vabdq_u8`, `vmull_u8` and `vpadalq_u16`. The bias-encoded inner product uses `veorq_u8`, `vmull_s8` and `vpadalq_s16`. Both agree bit for bit with the AVX2 specializations, which the tests require. Two invariants deserve a note: - The L2 path keeps an unsigned accumulator. A `vmull_u8` square reaches 255^2 = 65025, which an int16 lane would read as negative. - For x in 0 to 255, `x ^ 0x80` read as `int8` is exactly `x - 128`. That is how the kernel removes the +128 bias before `vmull_s8`. **2. Dispatch chains that list only x86 levels.** The `if constexpr` chains in `sq-dispatch.h` enumerated x86 levels only, so an ARM host fell through to the float path. This adds `ARM_NEON` to four chains: two in `select_distance_computer_body`, and two in `sq_select_InvertedListScanner`. The chain in `is_dimension_compatible` already included ARM. This does not add `ARM_SVE`. The scalar-quantizer entry points dispatch with a mask that holds no `ARM_SVE` bit, so an SVE host already falls through to the `ARM_NEON` case and now gets these kernels. Adding `ARM_SVE` would instantiate the empty primary template in `distance_computers.h`. This corrects that template's stale comment. **3. Level masks that hide existing SVE kernels.** The default mask holds no `ARM_SVE` bit, so the dispatch fell through `case ARM_SVE` to `ARM_NEON`. This uses `with_simd_level_a1` at every site where a real SVE kernel exists and links: `IndexFlat.cpp` at four sites, `AdditiveQuantizer::compute_centroid_norms`, `block_l2` in `SuperKMeans.cpp`, all three wrappers in `pq_code_distance-generic.cpp`, and `with_VectorDistance` in `distances_dispatch.h`. The `IndexFlat` sites matter most. `faiss::fvec_L2sqr()` already used the SVE mask, so on an SVE host the free function ran SVE while `IndexFlatL2`'s distance computer ran NEON. Also: `FAISS_SIMD_LEVEL=ARM_SVE` on a build without SVE compiled in used to skip every level and run at `NONE`, because `with_selected_simd_levels` has no case label for an uncompiled level. It now walks down to the nearest compiled level. The override is still honoured when the CPU lacks the level, since forcing a level is the point of it. Only uncompiled levels are corrected. The unused `AVAILABLE_SIMD_LEVELS_A2` is deleted. It is the NEON-to-NONE trap in constant form, with no users. This change keeps the existing mask names. A follow-up renames them to say what they hold. ## Out of scope In rough order of remaining value: - `IndexPQ.cpp` and `IndexIVFPQ.cpp` still pin PQ to `ARM_NEON` on an SVE host. A mask change is not enough. `pq_code_distance-sve.cpp` includes only `pq_scan_impl.h`, and `with_HammingComputer<ARM_SVE>` has no complete type. - `distances_aarch64.cpp` forwards five `ARM_NEON` specializations to `<SIMDLevel::NONE>`, so a non-SVE aarch64 host runs scalar code in the IVFFlat scan. - `rabitq_neon.cpp` forwards all six `ARM_NEON` specializations to `<SIMDLevel::NONE>`. There is no SVE variant. - There is no `block_l2<ARM_NEON>` and no `exhaustive_L2sqr_blas_cmax<ARM_NEON>`. - Part two of T287037898, which is SDOT and SMMLA. `FEAT_DotProd` and `FEAT_I8MM` are not expressible as a `SIMDLevel`. The right shape is a runtime `getauxval(AT_HWCAP)` check inside the ARM translation unit, which follows the `SIMDConfig::avx512_split` precedent. Note the reporter's caveat: SMMLA shows no improvement until the scan loop is tiled, so the tiling must land in the same change. Reviewed By: alibeklfc Differential Revision: D118682598 fbshipit-source-id: 1ab588d9fa130e8246bf996025fc11d8954323be	2026-09-10 09:32:36 -07:00
Trang Nguyen	5702cafcb7	Remove dead TurboQuant projection state (#5618) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5618 Remove the unused projection buffers and eager `init_projection` work from `ScalarQuantizer::TurboQuantRefine`. Quantizers construct the required projection from `trained` when used, so rebuilding it during training and deserialization only added an unbounded quadratic allocation and cubic QR operation. Keep `seed` and `qjl_type` as the serialized configuration, enforce that the helper remains a small config-only struct, and cover both projection modes in deserialization tests. ___ Differential Revision: D119243693 fbshipit-source-id: 53f982b00dd849cbe88983ffd27809c2fa738a4c	2026-09-09 11:05:57 -07:00
Trang Nguyen	545550f6a2	Use unittest assertions and f-strings in test_index_composite (#5571) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5571 `test_index_composite.py` used bare `assert` statements throughout. Inside a `unittest.TestCase` these are worse than the `self.assert*` helpers in two ways: a failure prints only `AssertionError` with no operand values, so you have to re-run under a debugger to see what the actual number was, and the whole assertion is compiled out under `python -O`, silently turning the test into a no-op. This converts every bare `assert` in the file to the matching `self.assert*` call (`assertEqual`, `assertTrue`, `assertFalse`, `assertNotEqual`, `assertGreater`) and replaces the two remaining printf-style format strings with f-strings. Mechanical change only — no assertion was strengthened, weakened, or reordered, and no test logic was touched. The `raise AssertionError()` idioms guarding `try`/`except RuntimeError` blocks are left alone; converting those to `assertRaises` would change control flow and belongs in its own diff. Split out of D118606761 so that the `IndexIVFFlatDedup::remove_ids` bug fix stays reviewable on its own. Note this file is exported to the open source facebookresearch/faiss repo, so this diff needs an OSS export alongside it. Reviewed By: mnorris11 Differential Revision: D118721255 fbshipit-source-id: b6933a6119955f2dbd7590f4e39632d700a537c4	2026-09-08 14:08:01 -07:00
Trang Nguyen	1e5780fbbf	Fix OOB read in Panorama::reconstruct via IndexPreTransform (T287094917) (#5562) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5562 Lionhead harness `faiss_rmdt_post_read_reconstruct_fuzzer` found a heap out-of-bounds read at `Panorama.cpp:171`, reported as `READ of size 5122903332` in `__asan_memcpy`. Decoding the 232-byte crash input, it is `IxPT -> IxPT -> IxPT -> IxFp` where every `IndexPreTransform` carries an **empty** transform chain and the innermost `IndexFlatIPPanorama` has `d = 0x4C565349 = 1280725833` (so `code_size = d * 4 = 5122903332`, exactly the ASAN read size), `ntotal = 0`, and an empty `codes` vector. Three independent defects combine: 1. `IndexFlatPanorama::reconstruct` never bounds-checks `key`. It overrides `IndexFlat::reconstruct`, which does have `FAISS_THROW_IF_NOT(key < ntotal)`, and drops the guard. Overriding `reconstruct_n` likewise removes `IndexFlatCodes::reconstruct_n`'s `i0 + ni <= ntotal` check. With `ntotal == 0` and empty `codes`, `reconstruct(0, ...)` memcpy's `code_size` bytes out of a zero-length buffer. `Panorama::reconstruct` takes an unsized `const uint8_t*`, so it cannot self-validate -- the caller has to. 2. The `IxFP`/`IxFp` read branch does not range-check `d`. It is the one index type that does not go through `read_index_header`, so it misses that function's `FAISS_CHECK_RANGE(d, 0, (1 << 20) + 1)` and `ntotal >= 0` checks. The `codes.size()` equality check below it does not catch this, because `ntotal == 0` makes `num_slots == 0` and an empty `codes` is then "valid". 3. `IndexPreTransform` deserialization skips all consistency checks when the chain is empty -- the `chain[0].d_in == ixpt->d` / `chain[nt-1].d_out == index->d` validation sits entirely inside `if (nt > 0)`. With `nt == 0`, `IndexPreTransform::reconstruct` passes the caller's buffer (sized from the outer `d`) straight to the sub-index, so a mismatched sub-index `d` is also a write-side overflow, for any sub-index type. Each is fixed: - `IndexFlatPanorama::reconstruct` / `reconstruct_n` now range-check against `ntotal`. - The `IxFP`/`IxFp` branch applies the same `d` and `ntotal` checks as `read_index_header`. - `read_index` requires `index->d == ixpt->d` when the `IxPT` chain is empty. Two adjacent gaps in the same audit are closed as well: - `IHfP` (`IndexHNSWFlatPanorama`) never validated `cum_sums.size()`, unlike the equivalent `IxFP` check. Both `get_cum_sum()` and `HNSW.cpp`'s Panorama search path index it at stride `pano.n_levels + 1`, so a short vector is an OOB read at search time. It also had no explicit `n_levels > 0` guard. - `ArrayInvertedListsPanorama::get_single_code` bounds-checked with `assert`, which is compiled out in opt builds. It reaches the same `Panorama::reconstruct` sink via `IndexIVFFlatPanorama::reconstruct_from_offset`. Reviewed By: mnorris11 Differential Revision: D118495504 fbshipit-source-id: 46bc7a1a6c9335a5589e20221b9478ae5505b9da	2026-09-08 13:56:04 -07:00
lyang24	7f4cedda9c	Add staged RaBitQ storage to HNSW (#5526) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5526 Reviewed By: junjieqi, mnorris11 Differential Revision: D116650696 Pulled By: alibeklfc fbshipit-source-id: 68ec701da84bd72a71e83ae5fadc041b2890eefe	2026-09-08 08:53:40 -07:00
Binozo	2ed4c106e9	Fix: Windows SIMD detection (#5497) ... Summary: Hi, while testing on windows x64 systems I've noticed that the `dd` optimization compilation target doesn't work properly. Causing crashes on non-avx2 systems for instance. This pr fixes the SIMD level detection. MSVC doesn't define `__x86_64__` but does define `_M_X64`. This is what this patch is based on. I got some nice [GitHub actions](https://github.com/Binozo/Faiss.NET/actions/runs/30251011773/job/89928775910) and tested the patch on it. ##### Based on https://github.com/facebookresearch/faiss/issues/5476 but reopened because I made a mistake while rebasing Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5497 Reviewed By: alibeklfc Differential Revision: D117897685 Pulled By: mnorris11 fbshipit-source-id: 80987895d17945bac9a4c5f0eb14beb67c84cbd5	2026-09-04 15:27:56 -07:00
kzahiri1	b4c66ba603	Fix reverse_index_factory/get_code_size round-trip for HNSW, IMI and IVFPQR (#5564) ... Summary: Three defects in `contrib/factory_tools.py` where a reversed factory string rebuilds a different index or fails to parse. `test_get_code_size_hnsw_roundtrip` already pins this invariant for flat HNSW; these cases escape it. 1. **HNSW storage dropped.** The `IndexHNSW` branch never read `index.storage`, so `HNSW32,SQ8` and `HNSW32,PQ16x8` both reversed to `"HNSW32"` and rebuilt as `IndexHNSWFlat`. `get_code_size` then applied the flat `d*4` formula: at d=128 it reported 768 bytes/vector for an index whose storage is 128 plus the 256-byte graph estimate, so 384. 2. **IMI regex fields transposed.** `index_factory.cpp:295` parses `IMI2x([0-9]+)`, but the regex read `IMI\d+x2`. Every real IMI key (`IMI2x10,PQ16`, and the ones in `demos/demo_auto_tune.py`) raised `RuntimeError("cannot parse")`. 3. **IndexIVFPQR matched by the IndexIVFPQ check**, dropping the refinement stage: `IVF64,PQ8+16` reversed to `IVF64,PQ8x8`, 8 bytes instead of 24. Consumers are `benchs/bench_all_ivf/parse_bench_all_ivf.py` (imports `get_code_size` as `unitsize`) and `benchs/bench_fw/index.py`. Flat storage stays implicit as the bare `HNSW<M>` string, and a null `storage` pointer still returns `HNSW<M>` instead of raising. **Behavior change worth flagging:** `IndexHNSW2Level` storage is `Index2Layer`, which `reverse_index_factory` does not handle, so it now raises `NotImplementedError` instead of silently returning a wrong `"HNSW32"`. It is not reachable from `index_factory`. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5564 Test Plan: Four tests added to `TestFactoryTools`. All four fail on unpatched `factory_tools.py` and pass with it: ``` # pristine contrib/factory_tools.py, new tests present 4 failed, 7 passed FAILED test_get_code_size_hnsw_non_flat_storage FAILED test_get_code_size_imi FAILED test_hnsw_storage_reverse_index_factory FAILED test_ivfpqr_reverse_index_factory # with the fix 11 passed ``` Full `tests/test_contrib.py tests/test_factory.py`, pristine vs branch: ``` pristine: 2 failed, 88 passed branch: 2 failed, 92 passed ``` Failure sets are identical. The two are `TestComputeGT::test_compute_GT_gpu` and `test_compute_GT_ip_gpu`, pre-existing and unrelated (`AttributeError: module 'faiss' has no attribute 'GpuMultipleClonerOptions'` on a CPU-only build). An A/B sweep over 40 factory strings changes exactly the 7 expected lines and nothing else: ``` - HNSW32,SQ8 IndexHNSWSQ HNSW32 768 + HNSW32,SQ8 IndexHNSWSQ HNSW32,SQ8 384 - HNSW32,SQfp16 IndexHNSWSQ HNSW32 768 + HNSW32,SQfp16 IndexHNSWSQ HNSW32,SQfp16 512 - HNSW32,PQ16x8 IndexHNSWPQ HNSW32 768 + HNSW32,PQ16x8 IndexHNSWPQ HNSW32,PQ16x8 272 - IVF64,PQ8+16 IndexIVFPQR IVF64,PQ8x8 8 + IVF64,PQ8+16 IndexIVFPQR IVF64,PQ8+16 24 - IMI2x5,Flat IndexIVFFlat IMI2x5,Flat <RuntimeError> + IMI2x5,Flat IndexIVFFlat IMI2x5,Flat 512 - IMI2x5,PQ8 IndexIVFPQ IMI2x5,PQ8x8 <RuntimeError> + IMI2x5,PQ8 IndexIVFPQ IMI2x5,PQ8x8 8 - IMI2x8,PQ8x8 IndexIVFPQ IMI2x8,PQ8x8 <RuntimeError> + IMI2x8,PQ8x8 IndexIVFPQ IMI2x8,PQ8x8 8 ``` flake8 at the 80-char limit from CONTRIBUTING reports the same 12 pre-existing findings before and after, none in the changed lines. 🤖 Generated with [Claude Code](https://claude.com/claude-code) Reviewed By: mnorris11 Differential Revision: D118661065 Pulled By: trang-nm-nguyen fbshipit-source-id: b50a9522361e3fd14f276b36196d3c728567b980	2026-09-04 11:14:06 -07:00
ethanglaser	cfbf4ec5ff	SVS: allow option to disable vector storing (#5525) ... Summary: Allow avoiding storing original vectors, which may not necessarily be used, in which case they would be wasting memory Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5525 Reviewed By: alibeklfc Differential Revision: D118722620 Pulled By: mnorris11 fbshipit-source-id: 9757fa3d272187308c750fb6c6d0e3a6e8ab2bb3	2026-09-04 10:02:36 -07:00
generatedunixname2238252550246476	c0084f5cd2	Clamp EDEN unbiased L2 distances to be non-negative (#5569) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5569 https://www.internalfb.com/monitoring/oncall_operator?board=1003685189388103&workItem=4614322948811275 --- `IndexEDEN` / `IndexIVFEDEN` with the unbiased 1-bit EDEN scale can return negative `METRIC_L2` distances, violating the contract that L2 distances are never negative. Root cause: for the unbiased scale, `distance_from_code_dot` in `faiss/impl/scalar_quantizer/EDENQuantizer.cpp` reports `query_base + l2_norm_term - 2*scale*<q_code, x_res>`, where the encoder sets `l2_norm_term = ||r||^2` (the *original* residual norm) rather than the reconstructed-code norm `scale^2 * ||q_code||^2`. Unlike the biased scale (where the three terms complete the square `||x_res - r_y||^2 >= 0`), the unbiased branch is an unbiased *estimator* of the squared distance, so for a query residual that aligns strongly with the code direction the subtracted term can exceed `query_base + ||r||^2` and the result goes negative. Every distance path (reference, LUT, and the AVX2/AVX-512 batch variants) routes through `distance_from_code_dot`, and none of them clamped the result. Fix: clamp the L2 branch of `distance_from_code_dot` to zero. This is the single choke point, so it covers every distance and search path. The clamp only floors estimates that were already below the true minimum of zero. Design note for reviewers: clamping biases the unbiased estimator upward for the very closest matches (whose estimates are the ones that dip below zero), and collapses their fine ordering at exactly zero. The alternative — leaking negative squared distances to callers that take a sqrt or compare against a radius — is worse, and this is the most reversible fix. If the team prefers to preserve the strict unbiased estimator and instead relax the non-negativity expectation, that is a larger design decision to make separately. Reviewed By: trang-nm-nguyen Differential Revision: D118611745 fbshipit-source-id: 8c3d6a279fb15a92697589909f89eca218915e52	2026-09-04 04:34:19 -07:00
Trang Nguyen	6457e941f5	Contain DirectoryArchiver entries within the extraction root (#5561) ... Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5561 `svs::lib::DirectoryArchiver::read_file` builds its output path as `root / filename`, where `filename` is read straight off the deserialization stream. Neither guard on that path contains it: - `std::filesystem::operator/` **discards `root` entirely** when the right operand is absolute, so `filename = "/etc/cron.d/x"` yields `path = "/etc/cron.d/x"`. - A `..` component climbs out of `root` normally. - `check_file(path, out|binary)` only verifies that `path.parent_path()` is an existing directory. It performs no containment check — and that check is satisfied by construction anyway, because `read_file` calls `fs::create_directories(parent_dir)` two lines earlier. The result is that `faiss::read_index_up()` on untrusted bytes can create or overwrite an arbitrary file with attacker-controlled content, bounded only by the process's filesystem permissions. The harness manifest already rates this surface `REMOTE` / `PRE_AUTH` / `ZERO_CLICK`. This is not theoretical. The new tests fail on unpatched code with `std::filesystem::exists(probe)` returning **true** — the file really is written outside the temp root. Note the deserialization then fails with an unrelated `"File could not be opened for reading"`, so the write is a silent side effect that never surfaces as an error to the caller. The fix normalizes both sides and rejects any entry whose resolved path is not under `root`, before `create_directories` runs so that a rejected entry leaves nothing behind. Legitimate entries are unaffected: plain names, nested `sub/dir/name`, `./name`, and interior `..` that stays inside `root` all still resolve normally — only escapes are rejected. `third-party/svs/v0.4.0` is pristine vendored code (`c5e5dbb35bbf`, never patched internally), so this also needs reporting upstream to Intel via their vulnerability handling process (`src/SECURITY.md`) rather than as a public PR, so it survives the next version bump. The related unbounded-allocation defect in `Archiver::read_name`, on the same call path, is fixed separately in the next diff in this stack (T287110736). Reviewed By: mnorris11 Differential Revision: D118494326 fbshipit-source-id: 7f7851111375eda831e4a7dac0acb7cdd1f80dc8	2026-09-03 13:01:21 -07:00