Skip to content
Development documentation for unreleased code on main. Behavior can change before a release. Latest release docs

Vector Search Internalsdev

Design of the vector indexing and search path: how per-segment FAISS aux indexes are recorded, built, and queried. The user-visible contract (query knobs, scoring, recall) is in guide/vector-search.md.

The stored vector column is the source of truth; ANN indexes are derived, per-segment aux overlays behind an engine seam. Exact flat KNN, cosine raw-column normalization, full-precision rescoring, and creation of missing overlays all read or regenerate from the column.

truncate_dims (Matryoshka prefix truncation) is applied before the column: the index handler validates the input length (dims, or truncate_dims for an already truncated vector), cuts the vector to its prefix, then runs cosine normalization, and the query parser cuts the query vector the same way. VectorFieldType::storedDims() is the stored dimension and inputDims() the declared input one, so the column, overlays, exact scan and rescoring see only the truncated vector and need no special casing; schema ann settings such as pq.m are validated against storedDims(). Truncation requires dims, since stored lengths can no longer tell models apart, and cosine, under which a prefix cut here and one renormalized by the provider score the same.

Vector aux indexes are recorded as segment overlays in the commit manifest. Each segment’s SegmentInfo can carry AuxIndexInfo entries whose vector kind is vector_faiss and whose opaque metadata is VectorAuxMeta.

A vector aux build is introduced during commit when build_aux_indexes selects a vector field or "*". Plain commits without vector selectors never build vector overlays. After a segment has a vector overlay, that overlay follows the segment by liveness: later commits carry it forward without checking the shard core generation. Delete-only commits keep existing overlays; deleted-document vectors remain in FAISS and are filtered at query time.

Explicit vector selectors also activate those concrete overlay names in the writer. That activation is process-local unless it produced a durable overlay entry. A commit whose vector build fails deletes its staged files, attaches nothing to its captured segments, and activates nothing itself. Attachment and activation on success precede data sync and manifest publication; the failure rule applies to the build. A selecting commit records its selectors when it captures its segments (see Merging). Startup seeds active names only from overlays already present in the commit manifest, so Luxir never treats intent-only state as a boot-time “must build” queue.

Explicit commit-time vector builds stage overlay files and entries across the whole selected commit. If any requested vector build fails, staged overlay files are deleted and no partial vector overlay entries are retained for a later plain commit to publish.

Rebuilding does not require document reindexing at the storage level, but the current public API cannot remove an existing per-segment overlay. The writer has an internal drop/rebuild seam; exposing a safe collection-level rebuild is future work.

Every overlay is an IVF index: k-means centroids route a query to inverted lists, and the lists hold one compact code per vector. The field’s schema ann settings pick the code (RaBitQ by default, or explicit PQ; see guide/vector-search.md); the builder reads them when it builds an overlay and records the codec and its build parameters in the overlay’s VectorAuxMeta, so the reader and query path never consult the schema to interpret an overlay. A codec change applies to overlays built afterwards. Segments with different codecs for one field are supported, not merely tolerated: each segment engine is constructed from its own overlay’s metadata, both codecs share the IVF list machinery, and the cross-segment list ranking compares centroid distances that are in the same metric space for both (see rotation below). RaBitQ query quantization (query_bits) is not an index property; it is read from the current schema at search time.

IVF+RaBitQ (default, ENGINE_IVFRABITQ) uses FAISS IndexIVFRaBitQ. RaBitQ (Gao and Long, SIGMOD 2024) stores, per vector, the sign bits of its residual from the list centroid plus two float factors, and estimates distances with probabilistic error bounds under its random-rotation model; extended RaBitQ adds magnitude bits per dimension. There is no codebook to train: building trains only the IVF centroids, unlike PQ, which retrains per-subspace k-means codebooks on every segment build and merge.

The error bound and unbiasedness assume the codes are taken in a randomly rotated space. FAISS does not rotate internally: RaBitQuantizer.h states “It is assumed that the Random Matrix Rotation is performed externally”. Luxir rotates with a seeded FHT-Kac transform (the rotator of the RaBitQ authors’ library) in util/VectorRotation.h, shared by the builder and the reader/query code. It uses exactly d coordinates, with no padding. Four rounds each apply random signs, then a normalized Walsh-Hadamard transform on the largest power-of-two block fitting in d, alternating head and tail. For non-power-of-two d, each round then pairs the first floor(d/2) coordinates with the last floor(d/2) coordinates in orthogonal sum/difference Kac steps. For odd d, the middle coordinate is covered by both Hadamard blocks. Power-of-two d skips Kac.

The signs use SplitMix64 from the recorded seed, consuming each word low bit first continuously across rounds; a set bit negates the coordinate. The rotation kind fixes this algorithm and bit ordering. Every step is orthogonal, so norms, inner products, cosine and centroid distances remain comparable with unrotated PQ segments. Application costs O(d log d), with O(d) cached signs, replacing the dense d x d matrix and its quadratic work. FAISS’s HadamardRotation pads to the next power of two, adding 33% code bytes at 768, 1536 and 3072 dimensions; avoiding that padding preserves code density.

Training samples and added vectors use the same transform. Headers are bare IndexIVFRaBitQ; metadata stores rotation kind and seed, with no matrix. Readers intern by (kind, dims, seed), and queries rotate once per distinct transform. A fixed seed shares the transform across overlays of one dimension. Confidence intervals remain empirical, rather than a deterministic guarantee. On five 1M corpora (128 to 1536 dims, L2, IP and cosine) it matched the dense rotation’s recall and latency at 1 and 2 bits, within the run-to-run variation of the k-means partition, and cut 1-bit build CPU by up to 23% (NQ 1536: vector build 12.0 to 8.2 s).

Each IVF engine slot binds an immutable prepared query: the canonical query for PQ, or the cached rotated query for RaBitQ, plus the current schema’s query quantization bits. Coarse assignment and both document and group scans use that same index-space query. Each scan call owns its selector and distance computer, with query quantization taken from the prepared query, so filtering, deeper rounds, and parallel list chunks share the same preparation policy without sharing mutable distance-computer state. Document and group scans share one traversal and result handler. PQ retains FAISS’s optimized code kernel; RaBitQ evaluates its 1-bit estimate and gates extra-bit work in Luxir. Exact column scans and terminal rescoring retain the canonical query.

Codes with one bit per dimension and a quantized query use RaBitQScorer. It owns its arithmetic: residuals are quantized by rounding half up and clamping, and estimates agree with FAISS within query-quantization error; last-bit float differences across builds and architectures are accepted. Tests check exact quantized values, bit planes and integer counts against a scalar reference, and factors and estimates against FAISS within a derived one-step tolerance. The scorer removes per-list allocation and bit-at-a-time packing, and the per-code virtual call. FAISS’s computer remains for extended codes and query bits 0.

RaBitQ’s estimated squared L2 distance can be negative. Since 1.15, FAISS clamps its 1-bit L2 estimates at zero; the port patch deps/ports/faiss/rabitq-negative-l2.diff removes that clamp so negative estimates keep their order. Internal ordering scores use 1 / (1 + d) for d >= 0 and 1 - d for d < 0, preserving ordering across segments and bounded cuts instead of tying negative estimates at 1. The common bounded handler inverts this map outward when setting its competitive distance threshold, admitting equal scores for identity ties. These approximate scores may exceed the public L2 range [0, 1]; terminal rescoring from column vectors restores exact scores before the final cut, similarity filtering, and returning results. Exact column witnesses bypass the bounded approximate heap, so an inflated estimate cannot evict an exact candidate. Public L2 scoring remains 1 / (1 + squared_distance).

FAISS also ships IndexIVFRaBitQFastScan, which block-packs codes 32 vectors at a time for SIMD lookups and measured about 1.5 to 2 times faster list scans in a standalone FAISS test. It is not used yet: its lists are BlockInvertedLists (padded 32-vector blocks with per-block factor regions), which needs a second mmapped list layout, and its search_preassigned rejects the per-call stats sink the parallel scan uses. The codec is recorded per overlay, so FastScan can arrive as another engine id.

IVF+PQ (explicit, ENGINE_IVFPQ) uses FAISS IndexIVFPQ with pq.m sub-quantizers of pq.bits bits each, unrotated. PQ’s automatic m is the largest divisor of dims under max(32, dims / 8) that leaves at least four dimensions per sub-quantizer, for every metric. If none does, use the largest divisor under the same cap. Explicit m is unchanged. Automatic m depends only on stored dims, including inferred dims, so it is stable across merges of the same dimension. It selects 48 / 96 / 120 / 192 / 384 at 384 / 768 / 960 / 1536 / 3072 dims.

The reader skips FAISS precomputation during deserialization. For L2 with by_residual, it explicitly enables the nlist * m * 2^bits-float table only when its bytes are at most ntotal * dims * 4, the raw vector bytes. Otherwise it disables the table and FAISS computes tables per list. This bypasses FAISS’s global 2 GB cap. With default sqrt(N) lists and m near d/8, the table is about 32/sqrt(N) of raw bytes; the bound primarily constrains explicit large nlist. IP/cosine has no resident L2 table. IndexReaderAuxTest.cosineSkipsL2PrecomputedTable pins both metric behavior and the size boundary.

The basis is the Cohere-768 cosine measurement below: m=96 improves recall over m=32, with code bytes and per-code scan work growing linearly with m (32 -> 96 bytes at 8 bits). The leading k-means work per training vector per iteration, and encode work per vector, remain 256 * dims at 8 bits: splitting the dimensions into more sub-quantizers does not multiply that arithmetic. This does not establish unchanged wall-clock build time; the build measurement below used m=32.

RaBitQ is the default, chosen on one-segment indexes at default probes plus 16 to 256 lists, single client: SIFT-128 L2, MIRACL-768 cosine, GIST-960 L2, Cohere-1024 IP, NQ-1536 cosine, Jina v5-small MS MARCO embeddings truncated to 256 / 384 / 512 / 1024 dims (cosine), all at 1M vectors, and OpenAI text-embedding-3-large 3072 IP at 500k.

From 384 dims up, 1-bit RaBitQ ran at about 0.5-0.8x PQ latency at equal or higher recall and built with equal or less CPU (0.39x at 3072 dims). Its intervals size the candidate pool per query, while PQ’s bounded count, fitted on one 1024-d IP corpus, left recall behind elsewhere: at 256 lists PQ reached .872 recall@10 on MIRACL (.975 with 1000 candidates), .710 on GIST at m=32 (.954), .949 on Jina-384 and .960 on OpenAI-3072, against .981-.997 for 1-bit RaBitQ. At 128 dims 1-bit RaBitQ took 1.16x / 1.30x PQ latency at k=10 / k=100, and 2-bit 1.03x / 1.02x at 0.55x PQ’s build CPU.

Automatic bits (0) resolve to 2 below 384 stored dims and 1 at or above. On the same model truncated to 256 / 384 / 512 / 1024 dims, 2 bits cut k=100 latency by 23% / 13% / 9% / 1% (21% on SIFT-128) but k=10 latency only below 384, while costing 1.5-1.8x the build CPU. 4 bits never beat 2.

GIST L2 with PQ m=32 topped out at .71 recall@10 at 256 of 1000 lists; m=120, now the automatic choice, reaches .94-.98.

These measurements predate the dimensions-scaled default probe policy and the dimensions-scaled automatic PQ m for IP/cosine. Here, “default” means sqrt(nlist) lists at every dimensionality, without the multiplier now applied above 128 dimensions. The default-recall and latency numbers below describe that earlier policy.

Tuning/BM_VectorAnnDataset (test/bench/VectorKnnBM.cpp) indexes a real corpus through the normal request path into 4 segments, builds every overlay with the production policy, and measures recall@10 of 200 held-out queries against the exact path plus serial single-query latency (gcc-release, i7-14700KF, shared with other builds). Two corpora:

  • 485,659 Cohere multilingual-22-12 embeddings of Simple English Wikipedia (768 dims, cosine).
  • SIFT1M (1,000,000 x 128, L2).

In this historical 768-dimension campaign, the tested 1-bit pools reached the same recall as the higher-bit codecs: 1, 2, and 4 bits all give 0.893 / 0.911 / 0.960 / 0.986 at nprobe default / 32 / 64 / 128, at the tested rescore pools. PQ at its then-automatic m=32 (32 code bytes) never passed 0.88, even with 500 rescored candidates; PQ with m=96 (96 bytes, close to RaBitQ’s 104) reached 0.886 / 0.902 / 0.950 / 0.970. The then-current bounded scans measured 1.2 ms for RaBitQ versus 0.66 ms for PQ m=96 at default nprobe. Those measurements predate shared floors, interval selection and amplitude storage; they do not establish a universal codec ranking or that 1-bit recall is generally list-limited. At 128 dims (SIFT) the defaults are close in recall (0.953 vs 0.960 at the default nprobe; 0.989 vs 0.999 at nprobe 128, where 2-bit RaBitQ or 500 candidates reach 0.9985 and 0.9965) and PQ is again faster. Overlay builds, including training and coarse assignment, took 10.2 s (RaBitQ, 140 B/vector) vs 16.7 s (PQ m=32, 55 B/vector) at 768 dims and 10.4 s vs 12.9 s at 128 dims. Bytes per vector include the 8-byte id and per-overlay headers (centroids, and for RaBitQ the stored d x d rotation).

The Cohere-768 cosine comparison motivating PQ’s automatic m=96 is:

PQ m Code bytes/vector (8 bits) Recall@10, earlier default probes Serial latency, earlier default probes Recall@10, nprobe 64
32 32 0.761 0.46 ms 0.784
96 96 0.886 0.66 ms 0.950

Build policy is per segment and size based. An IVF overlay is attempted only when the segment has enough vectors to satisfy the codec’s training floor and enough N * dims scan cost to justify an ANN index. Segments below either threshold stay on the flat-over-column path. This mixed composition is normal: a query can use FAISS for large segments and exact column scan for small segments.

The floors differ per codec for different reasons. PQ must train 2^bits centroids per sub-quantizer, and FAISS wants 39 points per centroid, so 8-bit PQ needs about 10k vectors. RaBitQ trains only the IVF centroids, which 39 points each cover from about 1.5k vectors, but training is not what binds. The original floor calibration also predates the dimensions-scaled probe policy: at nlist = sqrt(N), sqrt(nlist) lists probed at every dimensionality and about 194 candidates rescored for k=10, a single-threaded standalone FAISS measurement found the exact scan faster than an IVF+RaBitQ probe plus rescore below roughly 8k vectors, at both 768 dims (4k vectors: 0.25 ms exact vs 0.61 ms IVF; 16k: 1.74 ms vs 0.38 ms) and 128 dims (4k: 0.04 ms vs 0.07 ms; 8k: 0.10 ms vs 0.06 ms). The retained RaBitQ floor is 8192 vectors, close to the PQ floor, and the exact path keeps small segments exact.

The training set is a strided sample across the segment’s vector values, not a prefix sample. This avoids training only on the oldest values when data inside a segment is time ordered. The builder normalizes vectors for FAISS when the field uses cosine and the stored column is raw.

The sample holds ivfTrainingPointsPerCentroid (100) vectors per trained centroid: the IVF lists for RaBitQ, and the larger of the lists and the 2^bits codebook entries for PQ, whose codebooks train on the same rows. It is capped by the segment and by ivfTrainingSampleMaxBytes (2.5 GiB); the codec’s training floor still wins over that ceiling. FAISS asks for at least 39 points per centroid and subsamples above 256, so 100 sits between the two. A byte budget that ignores nlist starves large segments: 64 MiB at 768 dims is 21,845 vectors, 10 per list at 5M vectors, which produces uneven lists and lower recall at every probe count. K-means work is proportional to sample size times nlist, so at nlist = sqrt(N) training stays linear in N. The default nlist cap of 4096 bounds the sample at 409,600 vectors: 1.2 GiB at 768 dims and 2.4 GiB at 1536, so the ceiling does not bind either size. Each merge or commit build holds one sample copy until training finishes, charged softly to the index RAM budget without waiting for capacity. RaBitQ trains only the coarse quantizer, avoiding FAISS’s unused residual copy and assignment pass. PQ still trains on at most 256 residuals per codebook entry; its residual and optional subsample copies are also charged during training. A field with a large explicit nlist or thousands of dimensions reaches the ceiling first and gets fewer points per centroid. Larger samples cost build time: at 1M x 768 with an explicit nlist of 4000, the 1-bit build went from 14.0 to 42.7 s.

Raw-cosine training samples are normalized in place in their owned buffer. RaBitQ rotates the sample in place in row partitions; PQ needs no transform. Each add scratch buffer is limited by ivfAddChunkBytes (16 MiB by default), capped by available vectors with a minimum of one vector. Add uses up to two buffers for raw cosine plus rotation. Untransformed PQ add passes column bytes directly to FAISS. The serialized header’s nprobe is unused by Luxir: searches supply explicit probe parameters or selected lists.

OpenBLAS is built serial (with locking for concurrent callers), and a build gets its GEMM parallelism from TBB tasks in the indexing arena instead of a BLAS thread pool. A threaded BLAS would reach the query path: every level-3 call holds a per-variant lock for its duration, so a query’s rotation or coarse search would queue behind a build’s GEMMs, and on x86 OpenBLAS a one-column SGEMM still asks for a thread team at 768 dims and up. Measured on whole builds, partitioning across tasks was also faster than the thread pool and used far less CPU.

The arena observer pins FAISS OpenMP to one thread on every arena entry, including masters. All build and query parallelism comes from TBB tasks. The build partitions these steps in the indexing arena, isolating the caller so it cannot pick up an unrelated merge or flush while waiting:

  • Coarse assignment during training. The IVF’s actual quantizer is an IndexFlat subclass whose searches split rows, covering both k-means and residual-training assignment.
  • Add work for every codec. Each row slice normalizes when needed, rotates for RaBitQ, coarse-assigns with the base IndexFlat::search, and calls encode_vectors with list numbers. One serial add_sa_codes per chunk preserves input order within each inverted list.
  • RaBitQ training-sample rotation, in disjoint row slices in place.
  • PQ codebook training, one task per sub-quantizer with its own sub-vector buffer, clustering instance and flat L2 index. This mirrors FAISS’s default training path; residual precomputation follows after all tasks finish.

Row partitions have at least ivfBuildMinRowsPerTask rows (by default ceil(distance_compute_blas_threshold / dims) to retain FAISS’s BLAS path), up to four tasks per compute slot. Add chunks hold the larger of 16 MiB of input vectors and four times the arena compute width times that row floor, capped by available vectors, so scratch capacity scales with core count. The build subclasses serialize through FAISS’s dynamic_cast dispatch as plain IndexFlat and IndexIVFPQ; readers need no build-specific types.

Index data stays memory-mapped at query time. The aux file holds a small FAISS header (index parameters, IVF centroids, and the PQ codebooks) followed by the inverted-list payloads (codes and vector ids) in Luxir’s own layout; the reader decodes only the header into memory and serves list scans directly from the mmapped file. Residency of the bulk index data is therefore managed by the OS page cache, like the vector column itself, rather than forced into process RAM.

RaBitQ overlays also store upward-rounded float32 error amplitudes after the codes in inverted-list order: sigma1 for 1-bit, sigmaB for multi-bit (4 bytes/vector for every width). The multi-bit gate reads sigma1 from the code’s own f_error; the side amplitude is read only after that gate. PQ has no amplitude section. The builder computes these in the encoding row pipeline from the rotated original, assigned centroid and actual code. SigmaB is the residual reconstruction error norm divided by sqrt(max(1, D-1)), with a factor of two for squared L2. Sigma1 is computed from the sign reconstruction error before the fixed 1.9 confidence multiplier. These amplitudes support empirical confidence intervals; they are not deterministic error bounds. The reader exposes a mmap view, validates finite, non-negative amplitudes once at open and exposes per-list spans for sequential, unchecked scan loads. Metadata and footer version 3 validate the component count and file size; older formats fail on open and must be rebuilt.

VectorIndexBuilder::finishRaBitQCode writes the sign-bit factors for every code: dp_multiplier = ||r||^2 * sqrt(D) / sum(|r_i|) (zero when the sum is zero), sigma1, and upward-rounded f_error = sigma1 * 1.9 for multi-bit codes. FAISS still writes the sign bits, or_minus_c_l2sqr, and extra-bit codes and factors. This avoids FAISS’s small-norm guards (still present in 1.16.0): below a squared residual of FLT_EPSILON, its multiplier scores the residual as if it had unit length, and below sum(|r_i|) = 2 * FLT_EPSILON its error factor becomes zero. Such codes arise near centroids (duplicates, singleton lists, normalized-centroid rounding) and throughout small-magnitude L2 data. A false-high 1-bit interval can raise the witness floor and prune true neighbors at any probe count. The corrected factors preserve residual length and direction across scales, but the intervals remain empirical: for IP, float cancellation in FAISS’s 1-bit estimator leaves errors around 1e-7 even at zero amplitude, so they are not arithmetic-exact. The extra-bit factors have no such defect; in multi-bit search a bad 1-bit factor causes false gate rejections (a lost neighbor) or wasted extra-bit work, not false witnesses.

Before taking apart a RaBitQ wrapper, the reader checks the header’s bit count against the overlay metadata. Both codecs also check the header’s list count against that metadata, in addition to checking the list footer against the header. Mismatches reject the overlay with the conflicting values in the diagnostic.

Merges drop overlays for merged-away segments. The merged segment is treated as a new segment and gets fresh overlays inside the merge-private phase for active vector fields that pass the same thresholds. Whichever later commit publishes the merged segment publishes its overlay entries atomically with the segment. If a merge-time vector overlay build fails, Luxir deletes the staged overlay files, publishes the merged segment without vector overlays, and serves that field through the exact flat column fallback until a later explicit build succeeds or the segment merges again.

A merge finishing during a selecting commit’s build builds the selected overlays on its private output without waiting. The * selector matches the output’s own eligible fields. At swap, the merge prepares again only for an active name it has not attempted or an in-flight selector it has not matched. Failed names are not retried by that merge.

Every vector overlay installed with a merge output makes its name active for later merges. Thus a merge may retain a valid overlay even if the selecting commit’s build fails; that commit still attaches nothing and activates nothing itself. This agrees with startup seeding from materialized manifest overlays. A merge swapping before the commit captures its segments gets its overlay from the commit.

Source segments that the commit captured still get overlays from it even when a merge is replacing them, because that commit publishes them. Those builds are discarded once the merged output publishes.

KnnQuery creates one vector engine per segment. A segment uses its vec.<field> FAISS overlay when the work model prefers IVF, or scans the vector column exactly. Segments without an overlay, and nonempty columns with an empty ANN index, use the exact engine. The engines search inside the per-segment prepare domain, which is live-filtered and already holds every enclosing restriction: a boolean folds its filter clauses and, when a required or optional clause selects inside that domain (kNN, directly or nested), its prohibited (must_not) clauses into the domain it hands its children (outer AND filters AND NOT prohibited). The folded domain then replaces the boolean’s prohibited scorers as its required domain supplier, so each exclusion is materialized once, through the same filter cache uses as a filter clause.

Which constraints reach a kNN is decided on the logical query, before Weight creation, by one effective-role projection that both normalization and membership keys use, so it never depends on score demand or on whether required-clause inlining applies. When a boolean has a domain consumer under required or optional, required leaves with an automatic uniform score profile (ranges, prefixes, automata, exists, geo, term sets including any_of) take the filter role, since they add no score. The projection also extracts, by reference, the necessary non-scoring constraints of booleans reached through chains of required/filter children (looking through boost, constant-score and force-prepare wrappers): their filter, prohibited, and promoted leaves. That makes eligibility closed under AND re-association. It never follows an optional group (even with min_match) or a prohibited branch, and never extracts a domain consumer; extracted exclusions stay prohibited. A nested copy is dropped only while its boolean keeps another required clause, so rank-only optionals never become requirements, and a retained copy shares the extracted one’s query-owned filter use, which is request-owned when the shared cache rejects admission or is absent. Scoring siblings, including terms and constraints wrapped in constant_score(...), intersect with the kNN’s top-k afterwards. Required-clause inlining never moves a domain consumer to a different prepare stage.

FAISS ids are segment-local vector value ranks, so the query path maps each returned value rank back through that segment’s vector column metadata before liveDocs, filters, scoring, and multi-valued collapse.

IndexReader opens and pins overlay files eagerly when it opens an index version, so cleanup can unlink old files without breaking existing readers. The FAISS index bytes are decoded lazily on first kNN use and then cached on the segment reader.

Routing uses column and overlay metadata before loading FAISS or rank-liveness state. Single-valued eligibility counts are exact. Unfiltered multi-valued columns use upper bounds without a domain walk; IVF replaces their live-vector bound with the cached rank-liveness count. Filtered multi-valued counts sum value ranges for array domains or when the domain or its complement has at most 1024 docs. Larger bitset domains estimate vectors from eligible docs and average multiplicity. AUTO folds these domains in round one, obtaining the exact count before IVF sets selectivity and its stopping target. Cheap counts and rank-bitmap folds use the same doc-to-rank walk.

KnnPlanner prices predicted work with one calibrated unit-cost table. Exact slots pay per scored dimension, per visited domain doc and per rank mapping. IVF slots pay per examined entry, with an extra term for PQ (its FAISS scanner tests the selector through a virtual call) and a branch-misprediction term proportional to p(1-p) for selector pass rate p, except on 1-bit RaBitQ, whose selector test does not branch; per codec score (PQ subcodes; RaBitQ one-bit and extra-bit scores, each a constant per code plus a term per dimension); per list setup; per coarse centroid dimension; per slot-round; and per terminal read plus per terminal dimension. RaBitQ re-quantizes the query residual for every list, so its list setup scales with dimensions; 1-bit and extended codes have separate unit costs for scoring and list setup, since only the former use RaBitQScorer. PQ list setup is zero for inner product and cosine. Under L2 it scales with subquantizers while the segment keeps FAISS’s precomputed table; without it, FAISS computes a full distance table per list, priced as 2^bits * dims distance dimensions with an unfitted seed equal to the exact-dimension cost. Interval terminal reads have a shared floor of min(k, examined interval vectors), with dimensions scaled by the read-weighted average. Every query pays a request constant, and any query that runs IVF pays a second one. Units are nanoseconds divided by the cost of one exact dimension; counters expose the same units, and KnnPlanner::Costs records what they were fitted on.

For a configuration of IVF slots, predicted coverage is the maximum of initial coverage, bounded fill and the remaining document-unit obligation, capped at one; explicit nprobe pins it to initial coverage. Each IVF slot’s scan price is coverage * A + B plus a piecewise selector correction for resolving or folding the first round. Predicted rounds are one at initial coverage, otherwise 1 + ceil(log2(coverage / initial_coverage)). The bounded terminal allowance is one shared pool capped by eligible vectors; interval terminal reads are a dimension-dependent fraction of examined vectors, fitted for independent filters (anti-correlated filters read far more, and completion bounds that error). Filter placement is assumed independent of centroid order, and group diversity is not predicted from doc counts. RaBitQ extra-bit survival is a fitted function of dimensions until a segment has scanned; completion then uses the observed rate.

The planner compares all-IVF and all-exact with forward substitution sweeps from three seeds: all-IVF, every bounded segment exact, and every interval segment exact. The channel seeds handle the drop in bounded fill when the last bounded slot leaves. Only strict drops in total cost are accepted and ties retain IVF. Running sums, plus prefix sums over selector crossover fractions, keep the search O(segments log segments). Pinned effort is optimized exactly over the capped terminal terms. The adaptive search is a heuristic tested against exhaustive search, not a global optimizer. exact:true overrides routing. Exact slots contribute neither IVF fill nor its denominator.

Predicted cost is not a latency or recall guarantee: filter correlation, cold pages and multiplicity skew are outside the model. profile:true reports per-segment choices, eligibility, modeled costs, reasons and executed work. BM_VectorKnnFiltered exposes AUTO, forced IVF and forced exact modes with the raw counters used for calibration.

Filtered IVF round one chooses resolution or a rank-domain bitmap when predicted_checks * (resolve_cost - bitmap_cost) exceeds the fold cost; planning and execution share the rule. Dense single-valued bitset domains already are rank bitmaps and are borrowed without allocation. Other folds map doc IDs through forward column cursors: arrays walk members, bitsets the smaller of members and nonmembers, and multi-valued docs contribute their full vector ranges. Every deepen folds filtered domains, including interval-only breadth widening, and clears pooled ranks, so later scans use one bitmap probe without resolving IDs. Borrowed words are copied on the first pooled clear, and owned bitmaps are charged to the request memory tracker. The RaBitQ scan dispatches the selector kind once per scan and tests bitmaps inline; PQ uses FAISS’s scanner and its selector interface.

At each joined round boundary, the host previews the next allocation without advancing its cursors. If a slot’s cumulative IVF cost plus its next-round cost exceeds its full-domain exact cost, the slot completes exactly. This is a cost rule, not a regret bound. Explicit probe pins disable completion, and idle slots never trigger it. Completion removes the slot from allocation, recomputes effort over the active IVF slots, and runs one exact top-k pass over the slot’s full domain without pooled exclusions. Interval records and lower-bound witnesses stay valid. In document mode only the completed slot’s approximate candidates are retracted: nominees never evict across slots, so the active pool continues and deepens only if it falls short. Group admission can evict another slot’s members, so in group mode the active bounded pool starts a fresh epoch with covered lists rescanned and exclusions reopened. Profiles add the completion round, reason and costs; work counters include the abandoned IVF work and the exact pass.

Internally, an ivf.nprobe request becomes a scan fraction nprobe / sqrt(live_vector_count) applied across the current per-segment indexes; that is what makes the knob merge-stable. Engine-specific knobs are grouped under a per-engine sub-message on the wire (ivf today) so a second engine adds a sibling with its own units instead of overloading these; the host-side knobs (k, refine_candidates, exact) stay at the top level.

For per-segment IVF, Luxir ranks all segments’ IVF lists by query-to-centroid distance, then probes the globally best lists until the requested scan fraction is reached. List cost is based on that list’s live vector count divided by the live vector count of the IVF slots actually searched. Flat slots and empty filtered segments do not consume that budget. This handles uneven list sizes and avoids applying equal work to every segment. For an IVF segment with deletions the live count is exact: it rides along with the segment’s cached rank-liveness bitmap, which is rebuilt per delete generation in time proportional to the deleted docs (for a dense single-valued field the bitmap simply borrows the liveDocs bits). Filtered flat-scanned segments with deletions use a cheap upper bound for their live count instead. It contributes only to the whole-index reference breadth; the IVF allocation denominator uses exact live counts.

With default probes, the initial fraction expands by s^(-1/4), where s is the eligible-vector fraction over the searched IVF slots. Default effort scans about N^(-1/4) of an index (sqrt(N) lists, sqrt of them probed), and the same rule applied to the sN eligible vectors gives the exponent. On SIFT 1M and miracl 1M it keeps independent-filter recall at or above unfiltered recall at default effort; s^(-1/2) bought recall above that at about twice the latency for 10-30% filters. The fraction is floored by min_scan_fraction and capped at one. Explicit nprobe receives no selectivity expansion. All allocated lists are scanned before checking fill, even if exact slots already supply k units. Bounded document fill is capped by eligible docs in bounded IVF slots; document unit fill is capped by eligible docs across all slots. Default-probe queries also examine at least P0 * eligibleVectors selector-passing codes on newly scanned lists, where P0 is the initial fraction. Depth rescans and exact slots do not contribute. This is the eligible yield expected from an independent filter at P0; unfiltered scans already satisfy it through coverage. It allows binomial sampling slack of 2 * sqrt(target), at most a quarter of the target, so a filter independent of the lists does not pay an extra round for noise. Exhaustion, a full candidate pool or explicit probe pins end widening even if obligations remain unmet.

The host owns cumulative scan fractions and explicitly requests depth or breadth. For each unmet count obligation, it projects covered * need / have * 1.25, or covered * 2 when yield is zero. The next target is the largest projection, floored at the next globally ranked list’s fraction and capped at one. The allocator reports actual coverage, including whole-list overshoot. These remain effort heuristics: bounded selection and empirical interval pruning can miss neighbors even at full coverage.

Scan tasks return work totals, reduced at each round barrier into per-segment query state: physical entries, selector passes (with new-list passes separate), PQ scores, RaBitQ one-bit and extra-bit scores, list setups, depth revisits, flat scores and domain visits. Terminal scoring adds its column reads after each read-stage barrier. These count scoring work, not physical page IO; allocator liveness probes are counted separately and priced as rank-bitmap work, including the next-list lookahead under deletes.

Probed lists are always scanned in full. Entries within an IVF list are stored in insertion order, not relevance order, so a partial list scan would drop arbitrary candidates. nprobe selects lists; codec gates and terminal selection determine the work performed on their values.

Candidate selection has independent bounded, interval and exact channels. PQ defaults to k + 24 + ceil(15 * k^0.8); explicit refine_candidates selects the bounded policy for every approximate codec. Default RaBitQ uses intervals for every bit width. Exact column slots supply distinct-unit top-k results outside the approximate quota.

The bounded channel uses a shared R-th estimate floor. Its fresh DEPTH epochs exclude banked ranks and reset that floor. Its document budget, multiplicity inflation and group member caps apply only to bounded candidates. Interval selection is complete after traversing the selected lists, independent of retained count, and never requests DEPTH. BREADTH visits only newly allocated lists and preserves interval witnesses and retained identities. A mixed query must satisfy the bounded channel’s own obligation; interval hits cannot fill its quota. The result contract reports bounded completion separately from remaining breadth. Insufficient distinct units can trigger more breadth: bounded Groups continue BREADTH when the document pool is full but holds fewer than k groups.

For RaBitQ, the query-owned collector tracks each unit’s best lower endpoint and the k-th highest of those endpoints. A unit is a (segment, document) pair or a canonical CollapsePlan group key, including missing-key policy. A value is retained only while its upper endpoint reaches both the global witness floor and its own unit’s lower endpoint. Multiple values of one unit can remain competitive. PQ point estimates never witness the true k-th score. Exact column scores may witness it. Document units use a flat hash map from packed (segment, document) to reusable stable slots; only Groups copy and hash canonical CollapsePlan keys. Map, slot and key storage are request-accounted.

One-bit uses its single estimate with sigma1 * g_error * 1.9. Multi-bit first tests the optimistic 1-bit endpoint with gate epsilon 1.9, then constructs the full-bit interval with sigmaB * g_error * 1.9. The gate uses the witness floor for intervals and the R-th estimate floor for bounded collection. For L2 the raw distance endpoints are mapped in reverse order through the score transform, with outward rounding and upper scores clamped to 1. Scans reject in distance space against a cached outward threshold, converting only when the floor changes. Only admitted records pay for score mapping and outward endpoints. Both constants are empirical confidence choices, validated on IP at 128 and 1024 dimensions; they are not containment guarantees.

Terminal scoring starts with the best estimated value per unit, choosing k distinct units. All bounded candidates are mandatory in this stage too (bounded Groups nominations expand to their whole document). Exact scores are reused. Then T = max(k-th exact seed score, pessimistic witness floor) selects the remaining interval values by upper >= T. A value whose upper score is below its unit’s best known exact score is also skipped. Both stages read in segment and value-rank order, with disjoint column reads and a shared exact-score cache. Final unit collapse and similarity filtering use exact scores. Before similarity filtering, a diagnostic reports an unsupported floor and its distinct-unit shortfall when fewer than k exact units reach the final witness floor; it changes no selection behavior and does not detect every invalid interval.

There is no interval retention cap. RequestMemResource charges records, canonical unit keys, witness heaps, pending batches and terminal selection storage to the request’s existing opt-in byte ceiling. Exceeding it throws request_memory_exceeded, including from scan tasks; cancellation and joining precede destruction of shared state. Bounded candidate limits and explicit probe pins remain separate policies.

A single query’s scan and rescore run in parallel when the request executes in parallel mode. The selected IVF lists are split into contiguous per-segment chunks sized by their actual vector counts, and each chunk (plus each column-scanned segment) is scanned as an independent task; the terminal full-precision rescore runs one task per segment whose candidate bucket exceeds a small grain (smaller buckets, including the common small-k single-segment pool, fold inline on the calling thread).

All IVF chunks and segments share a bounded cut per fresh epoch and persistent interval witness state for the query. Task-local handlers batch admissions and canonical keys; group bounded handlers keep their local capped admission. Serialized updates publish monotone scalar floors. PQ uses its optimized kernel with floor refreshes between 256-code blocks. 1-bit RaBitQ scores a block and then admits its rows in order; extended RaBitQ uses its distance computer per code in the common traversal. Peak and terminal retained counts, seed and remaining reads, gate rejections and extra-bit evaluations accompany the selector-passing scan count in the benchmark stats seam.

Task boundaries do not depend on execution mode, and bounded cuts use a total identity order. RaBitQ confidence pruning can nevertheless change work and rare approximate misses with scheduling, since the floor seen during a scan depends on which tasks have published results.

  • Bulk ANN index data is paged by the OS rather than loaded into process RAM, so indexes larger than RAM still work.
  • Because the column is the source of truth, ANN indexes can be rebuilt or retuned per segment without reindexing any documents.
  • Segments below the training threshold, and segments whose build failed, are searched exactly from the column. A failed build leaves no partial state.
  • Exact results retain deterministic ordering across execution modes. Approximate confidence pruning can produce different candidates as task scheduling changes the shared floor.