IVF-SQ

Position

IVF-SQ preserves the IVF partitioning model and replaces every residual f32 component with an 8-bit scalar code. It usually occupies about one quarter of IVF-FLAT's vector payload. Unlike IVF-PQ, each dimension is quantized independently, so there is no subquantizer-count parameter or codebook lookup table.

Build and search

1. Train the IVF coarse centroids and assign training vectors to lists.
2. Compute per-dimension residual extrema using partition-local reductions, then pool them across the training sample. This avoids clipping unseen vectors to the narrow or constant bounds of sparsely sampled partitions.
3. Encode every residual coordinate to an unsigned byte. New indexes use pooled residual bounds for every list; existing v1 files retain their recorded per-list bounds.
4. At query time, select nprobe lists, reuse cached partitions, and load missing sorted row IDs and codes in bounded multi-range batches. Scan the codes with the metric-specific kernel and retain the top K. Blocked L2 scans use SIMD and a conservative partial-distance cutoff.

Cosine input is normalized through the shared metric preprocessing path. Filters are checked while scanning, so excluded rows do not enter the top-K heap.

Configuration

index.type = ivf_sq
dimension = 128
nlist = 1024
metric = l2
ivf.coarse-assignment = auto

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

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.

The scalar code width is fixed at 8 bits in v1. There is deliberately no sq.bits, graph-width, or search-width option.

Stable v1 storage

Every non-empty list is sorted by signed row ID before writing. Codes come first and are transposed within up-to-32-row blocks, with dimension before row lane, so SIMD evaluates multiple candidates together and the reader scans directly from the list payload allocation. The trailing IDs use the shared delta-varint encoding and remain aligned with code lanes. The normative byte layout and golden fixture are in the storage-format specification.

Open-source comparison

Faiss IVF-SQ provides residual SQ4/SQ6/SQ8/F16 encodings, parallel add, and query-parallel scanning over generic inverted lists. Milvus Knowhere builds on the same scanner model and adds concurrent inverted-list mutation. This implementation deliberately fixes the first immutable format at SQ8, stores per-dimension residual bounds in each list’s metadata, stores compressed sorted IDs instead of fixed eight-byte IDs, and transposes each 32-row code block for its CPU SIMD kernels.

Non-cosine inputs are borrowed, residual extrema are reduced in parallel without a training residual matrix, and assigned rows are encoded directly with precomputed scales and packed NEON/AVX2 conversion. The persisted layout is unchanged. SQ4/SQ6 would overlap IVF-PQ/RQ, quantile clipping would introduce another corpus-sensitive accuracy parameter, and compressing the relatively small resident bounds would save little beside the N × d code payload. The existing codes-first payload already allows one bounded multi-range operation and reuse of the read allocation as the scan buffer.

I/O and batching

Open reads the fixed header and contiguous resident metadata in two positional operations; the unified type dispatcher reuses that header. On a cache miss, a query submits selected list ranges through the abstract positional-read interface in capability- and 64 MiB-bounded multi-range batches. The historical uncached measurements below use one payload round per query for SIFT1M and GloVe-100 at nprobe=64; GIST1M averages 1.9. Batch search first deduplicates the lists selected across queries, loads each missing unique list once across the bounded rounds, and then scans queries in parallel. This is especially useful when a remote adapter executes the supplied ranges concurrently.

The add path retains the caller's L2/IP slice without copying it, partitions assigned row positions by list, and encodes those lists in parallel. Each active list task precomputes one d-component scale vector and fuses residual subtraction with quantization directly into the destination codes; the add path never materializes an N × d residual matrix. The writer retains only each list's row-order permutation and encoded IDs. It transposes lists in parallel within 16 MiB batches, writes them in physical order, then releases those buffers. A list larger than the batch budget is processed on its own.

During scanning, a candidate whose distance cannot improve a full Top-K heap is rejected before row-ID hashing. Batch scanning keeps one heap per query across loaded lists, avoiding per-list heaps and result merging. L2 scans may reject a complete 32-row block when its nonnegative partial distances cannot improve the current heap; returned candidates retain their complete distances. Single-query batches use the ordinary partition-parallel search path.

VectorIndexReader::open, open_with_options, and the language bindings use the reader memory budget (4 GiB by default) for a FIFO cache of decoded partitions. Resident metadata, cache slots, queue storage, and retained payload capacities are charged before insertion. Hits share immutable payloads without copying or positional I/O; filters and scores remain query-local. Oversized streamed lists bypass the cache. Zero budget disables caching, while required metadata still loads; transient query allocations are outside this retained-cache limit. Direct IVFSQIndexReader::open retains uncached behavior; use its open_with_options to enable caching. See reader options.

Populate the cache by replaying representative queries through search or search_batch. For IVF-SQ, optimize_for_search and warmup_queries only ensure resident metadata is loaded; they do not prefetch partitions.

On cache misses, IVF-SQ still reads complete selected lists. At high nprobe, scan bytes grow linearly; DiskANN is the better fit when the workload requires small page-granular reads from a large local-SSD index.

Public benchmarks

September 2026: optimization results

Three-run native ann_bench medians on Apple M4 Pro (12 CPU cores, 48 GiB RAM), with Rust 1.95 release builds, eight workers, nlist=1024, nprobe=64, k=10, 65,536 training rows, and 1,000 held-out public queries. Baseline commit 8dcabf2 and the current implementation use the same input files and settings; GloVe is L2-normalized.

Values show baseline → current. Build time includes training, encoding, and serialization. Sequential queries can reuse earlier partitions with the current 4 GiB reader budget; batch timing uses a separate fresh reader and includes payload reads and cache insertion. The baseline reader does not cache SQ partitions.

File sizes are unchanged. These warm local-filesystem measurements do not establish performance on cold storage, object stores, or other architectures and distributions. Pooled bounds can lose resolution on extreme-outlier data. See the reproduction guide and the current build and local-search tables.

Historical uncached implementation

The following measurements predate pooled bounds and partition caching. They use nlist=1024, nprobe=64, k=10, and 12 Rayon workers on Apple M4 Pro. Keep them separate from the current eight-worker comparison above, which now includes a GIST rerun.

Compared with the immediately preceding implementation on the same files, peak RSS dropped by 56–61%, local P95 improved by 3–8%, and batch throughput improved by about 8–61%, depending on dimension and cache behavior. File bytes and read bytes are unchanged.