faiss

2,354 Commits 268 Branches 33 Tags

3 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
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

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

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