IVF-RQ

Positioning and trade-offs

Design and distance estimation

The full estimator is exact for a query equal to the encoded source vector, while ranking other vectors through the scaled reconstruction. L2, inner product, and cosine have metric-specific additive/rescale factors; cosine inputs are normalized before IVF assignment.

Usage

Map<String, String> options = new HashMap<>();
options.put("index.type", "ivf_rq");
options.put("dimension", "128");
options.put("nlist", "1024");
options.put("rq.bits", "4"); // optional; 4 is the default
options.put("metric", "l2");
// options.put("ivf.coarse-assignment", "exact"); // optional; default auto

try (VectorIndexTraining training =
             VectorIndexTrainer.train(options, trainingVectors, trainingCount);
     VectorIndexWriter writer = new VectorIndexWriter(training)) {
    writer.addVectors(rowIds, vectors, vectorCount);
    writer.writeIndex(vectorIndexOutput);
}

try (VectorIndexReader reader = new VectorIndexReader(vectorIndexInput)) {
    VectorSearchResult result =
            reader.search(query, new VectorSearchParams(10, 64));
    int storedBits = reader.metadata().rqBits();
}

let config = VectorIndexConfig::IvfRq {
    dimension: 128,
    nlist: 1024,
    bits: 4,
    metric: MetricType::L2,
    use_approximate_coarse_assignment: true,
    ivf_train_max_points_per_centroid: 256,
};
let params = VectorSearchParams::new(10, 64);

Estimated-distance range search

The Rust VectorIndexReader and IVFRQIndexReader support single/batch range search, with or without a serialized Roaring allow-list, using the shared DistanceBand, VectorRangeSearchParams, and RangeSearchResult. L2, cosine and inner product are supported with fixed positive nprobe. Cosine normalizes queries before probe selection and rotation; each metric uses its own query terms and stored factors. Returned scores remain internal distances, not public inner-product similarities. See the shared usage examples.

Each eligible row is evaluated using its one-bit estimate or full multi-bit estimate from all stored bit planes. Membership is the half-open test lower <= estimate < upper, not a comparison against the original vector's exact distance. Negative estimates remain negative. Quantization can cause both missing rows and extra rows relative to an exact-distance band, even with every list probed.

Unlike top-K, range search does not use the coarse error-bound or quantized FastScan pruning stages: those do not certify membership in an estimate band. It uses F32 lookup sums for every allowed row, then hands the estimate to the shared collector. Probe selection computes direct L2 distances to every centroid, rejects non-finite values, and reuses selected distances in the estimate. A bounded candidate buffer uses O(nprobe) distance-selection storage per query, without skipping distance validation for unselected centroids. This range-only path uses the same calculations for single and batch queries, rather than top-K's SGEMM probe optimization. Lists are read once per call and shared across queries; sufficiently large scans run in parallel. Results have no fixed-K truncation, padding, or ordering guarantee.

Range statistics are returned with the result. rows_scanned counts filter-eligible rows, early_abandoned is zero, and list_reads counts unique non-empty lists. The last top-K statistics and all existing top-K behavior are unchanged. No storage-format change or C/JNI range binding is introduced.

Parameters

Larger training samples increase training work and may improve centroid quality. These limits apply within the Trainer reservoir of max(65536, 64 × nlist) vectors; increasing them does not enlarge that reservoir. See the shared training options for sampling and Paimon integration details.

Public-corpus measurements

Apple M4 Pro, 12 Rayon workers, one million base vectors, 1,000 published queries, nlist=1024, nprobe=64, Top-10, warm APFS pages. Times are release-build measurements from 25 July 2026.

On SIFT1M, a controlled bit sweep produced Recall@10 0.7233 / 0.8365 / 0.9149 / 0.9530 / 0.9731 for 2 / 3 / 4 / 5 / 6 bits. The compact v1 factor layout removes four unused bytes per row, reducing the corresponding files from 58.3 / 74.3 / 90.3 / 106.3 / 122.3 MB to approximately 54.3 / 70.3 / 86.3 / 102.3 / 118.3 MB without changing the distance estimator. Four bits is the first point above 0.90 and is therefore the default.

The fixed-latency rows model one concurrent multi-range round and do not model bandwidth, retries, TLS, or throttling. Batch QPS is one 1,000-query call, not independent clients.

v1 storage layout

The header records logical and padded dimensions, metric, required layout flags, persisted rq.bits, total vectors, rotation seed/rounds, plane bytes, rotation type 2, and compact factor layout 3. Every non-empty list begins with base_id, encoded-ID length, and code length, followed by sorted delta-varint IDs.

Within each 32-vector block, bytes are ordered by plane, byte position, then lane. For more than one bit, the five structure-of-arrays fields are coarse (f_add, f_rescale, f_error) followed by full (f_add, f_rescale). The omitted full error was never read: the full estimate is the final ranking stage and does not produce another lower bound. Readers reject the old pre-release layouts rather than guessing their meaning.

Capacity estimate

For one bit, only the two estimate factors are stored, so the factor term is 8 bytes. For 2–8 bits it is 20 bytes. The formula excludes small per-list headers and delta-varint ID variability.

Tuning order

1. Run IVF-FLAT with the target nlist/nprobe to establish the partition recall ceiling.
2. Start IVF-RQ at the default four bits.
3. If recall is low for both indexes, increase nprobe. If only IVF-RQ is low, try five bits before increasing I/O through more lists.
4. Compare the current IVF-SQ recall and scan results when one byte per dimension fits; compare IVF-PQ when minimum size matters.
5. Validate the final choice on a public or production corpus, including batch and the real storage adapter.

Implementation boundaries

• The file is immutable; updates require a new index file.
• Distances are approximate and raw vectors are not retained for exact reranking.
• Four transform rounds and compact factor layout 3 are fixed for v1; readers reject other values.
• Batch scan parallelism uses Rayon while sharing each loaded list payload across queries; a single query also scans independent lists in parallel once its candidate count reaches 8,192.
• optimize_for_search() loads and validates resident metadata; it does not change search results.