IVF-FLAT

Positioning and trade-offs

Design and data flow

Build

Search

1. Apply the same preprocessing used during construction.
2. Measure the query against every IVF centroid and select the closest nprobe lists.
3. Read those list payloads through the offset table in bounded concurrent multi-range calls.
4. Decode row IDs and compute the true metric against every raw vector. A Roaring filter skips disallowed IDs.
5. For at least 1,048,576 distance components, scan independent lists on Rayon workers. Batch search keeps list-major locality and scans every loaded list for all queries that selected it.
6. Merge list-local results in the original list order. Missing entries are padded with -1 / f32::MAX.

Public-corpus measurements

Apple M4 Pro, 12 Rayon workers, one million SIFT/GIST vectors or 1,183,514 GloVe vectors, 1,000 published queries, nlist=1024, nprobe=64, Top-10, and warm APFS pages. Times are release-build measurements from 25 July 2026.

The remote model groups every query's selected ranges into calls capped at 64 MiB. SIFT/GloVe average one round; GIST averages five because its raw-vector payload is much larger. Fixed 2/20 ms latency therefore produced P95 7.31/21.80 ms on SIFT, 29.73/130.49 ms on GIST, and 6.60/21.22 ms on GloVe. Batch throughput was 6,763/3,076 QPS on SIFT, 846/349 on GIST, and 7,394/2,948 on GloVe. These modeled numbers do not charge bandwidth, so they should not be read as evidence that transferring tens or hundreds of MiB directly from an object store is cheap.

Usage

The trained state is one-shot: finish training, pass the state to a Writer, add production vectors in batches, and serialize one index file. Readers discover the type from the header.

Map<String, String> options = new HashMap<>();
options.put("index.type", "ivf_flat");
options.put("dimension", "128");
options.put("nlist", "1024");
options.put("metric", "l2");

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)) {
    reader.optimizeForSearch();
    VectorSearchParams params = new VectorSearchParams(10, 16);
    VectorSearchResult result = reader.search(query, params);
}

let config = VectorIndexConfig::IvfFlat {
    dimension: 128,
    nlist: 1024,
    metric: MetricType::L2,
};
let params = VectorSearchParams::new(10, 16);

Parameters

v1 storage layout

The file is little-endian and has no outer container. The magic constant is IVFL / 0x4956464C; raw file bytes appear in reverse ASCII order because the integer is serialized little-endian.

Fixed 64-byte header

Offset table and list payloads

Each offset entry is (offset: i64, count: i32, id_bytes_len: i32), or 16 bytes. The Reader validates that list counts match the header before serving a query. A non-empty list contains:

Capacity estimate

For N=1,000,000 and d=128, vector payloads alone are about 488 MiB. Sorted delta-varint ID size depends on ID continuity and cannot be estimated as a fixed eight bytes. With nlist=1024, coarse centroids add about 0.5 MiB.

Tuning order

1. Fix the metric. Build exact ground truth with the production metric and include zero-vector edge cases for cosine.
2. Start automatic. Supply the final corpus count, inspect the resolved nlist, and use automatic query width.
3. Calibrate only if needed. Sweep explicit nprobe around the automatic value and record Recall@K, P95/P99, selected lists, and bytes read.
4. Measure batch search. Readers submit bounded multi-range batches, which often matters more than single-query latency on object stores.
5. Only then compress. Try IVF-SQ for a one-byte-per-dimension scan, IVF-PQ for stronger compression, or IVF-RQ for the strongest measured compact-IVF recall.

Implementation boundaries

• Index files do not contain checksums; the outer Paimon file and manifest layer provides integrity.
• Roaring64 filters are query payloads. Negative row IDs cannot match the RoaringTreemap domain.
• Readers reject unknown versions, non-zero reserved bytes, unknown flags, negative counts, mismatched total counts, and out-of-bounds sections.
• The search-only list payload owns an aligned f32 allocation and reads bytes into it directly; the public list-materialization API still returns owned row IDs and vectors.
• optimizeForSearch() does not change files or results; for IVF-FLAT it preloads centroids and the offset table in one contiguous read. The unified Reader reuses its type-dispatch header, so open plus metadata initialization takes two read rounds.