IVF-PQ

Positioning and trade-offs

Design and data flow

Product quantization

A vector is divided into m contiguous subvectors of dimension dsub = d / m. Each subspace trains 256 centroids. Encoding stores the nearest centroid as one byte. Search does not fully reconstruct vectors: it builds a 256-entry distance table for each subspace and sums m lookups. This is asymmetric distance computation (ADC).

Training and writing

Search

1. Normalize and apply the same OPQ rotation, then choose nprobe IVF lists.
2. Build an ADC table for each probed list. L2 residual mode can reuse precomputed terms.
3. Sum code lookups without loading raw f32 vectors.
4. Apply the optional Roaring row-ID filter and merge global top K.

What OPQ changes

Standard PQ splits consecutive dimensions. When information is unevenly distributed, some sub-codebooks become crowded while others are underused. OPQ learns a d × d orthogonal rotation that redistributes information before PQ while preserving Euclidean geometry.

Usage

Map<String, String> options = new HashMap<>();
options.put("index.type", "ivf_pq");
options.put("dimension", "128");
options.put("nlist", "1024");
options.put("metric", "l2");
options.put("pq.code-ratio", "0.0625"); // optional; default 0.0625
options.put("use-opq", "false"); // optional; default false

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)) {
    // Builds the reusable table for residual-L2 PQ.
    reader.optimizeForSearch();
    VectorSearchParams params = new VectorSearchParams(10, 16);
    VectorSearchResult result = reader.search(query, params);
}

let config = VectorIndexConfig::ivf_pq(
    128,
    1024,
    MetricType::L2,
    false,
)?;

The default relative code budget resolves this 128-dimensional 8-bit index to m=32. Option maps can change the target with pq.code-ratio or set pq.m explicitly. The resolved concrete m, rather than the ratio, is stored in the file.

Parameters

v1 storage layout

Fixed 64-byte header

Flags: bit 0 means OPQ is present; bit 1 means residual PQ; bit 2 means delta-varint IDs (required in v1); bit 3 means transposed codes (required in v1).

List payload

An offset entry is (offset: i64, count: i32, id_bytes_len: i32). A non-empty list stores base_id: i64, id_bytes_len: i32, the ID stream, then transposed codes. The 8-bit layout is codes[sub][vector]. The format also defines a 4-bit layout with two subquantizers per byte.

I/O and batching

The Reader loads the fixed header in one positional read and the contiguous OPQ matrix, IVF centers, PQ codebook, and offset table in one further read. The outer type dispatcher adds one small magic read. A query then supplies all selected non-empty list ranges in one capability-bounded multi-range round instead of issuing one request per field or list.

Batch search deduplicates the union of probed lists, sorts them by persisted offset, reads every unique list once, and scans queries in parallel. A single query uses the same physical-order read plan, which avoids backward seeks for a serial fallback SeekRead. Each query reuses its distance-table and candidate-distance scratch across lists. Internally, the Reader receives list bytes directly into a 16-byte-aligned typed allocation and exposes the persisted code suffix as a borrowed slice, avoiding a second code allocation; public list materialization continues to return owned arrays. The common one-byte row-ID delta has a checked fast path, and an 8-bit scan initializes distances from the first code column instead of zero-filling the scratch in a separate pass. The persisted codes[sub][vector] layout already matches this table-driven scan, so the improvements remain compatible with IVF-PQ v1.

The writer keeps only each list's row-order permutation and encoded IDs, performs a 32×32 cache-blocked transpose, and reuses one list-sized output buffer across all lists. It never retains an index-sized sorted-code copy. Same-machine SIFT/GIST serialization changed from 47 / 221 ms to 36 / 150 ms, and the reference transpose test plus v1 golden fixtures verify unchanged output bytes.

Capacity and memory estimates

Add 4d² bytes when OPQ is enabled. For N=1,000,000, d=128, m=16, nlist=1024, code payloads are about 15.3 MiB, versus about 488 MiB for IVF-FLAT raw vectors, before IDs and model sections.

optimize_for_search creates an in-memory residual-L2 table of about nlist × m × 256 × 4 bytes. The example above uses about 16 MiB. This table is not written back to the file.

Tuning order

1. Measure IVF-FLAT with identical nlist/nprobe to establish the no-quantization baseline.
2. Start with pq.code-ratio=0.0625, then sweep nearby ratios; compare resolved m, file size, Recall@K, and P99 together.
3. With the PQ budget fixed, sweep nprobe to separate coarse-partition misses from PQ rank error.
4. Test OPQ only when PQ loss is visible and the training budget allows it.
5. Call optimizeForSearch() once for long-lived Readers so precomputation is outside the hot path.

Implementation boundaries

• The public options API has no pq.nbits; unified construction creates 8-bit PQ.
• L2 uses residual PQ. Inner product and cosine currently use by_residual=false.
• The OPQ rotation, IVF centroids, and PQ codebooks are all stored in the file; Readers need no external model.
• Training samples should represent production data. Distribution drift can degrade both IVF assignment and PQ codebooks.