docs/ivf-rq.html - paimon-vector-index - Git at Google

 <!--
   Licensed to the Apache Software Foundation (ASF) under one or more
   contributor license agreements. See the NOTICE file distributed with
   this work for additional information regarding copyright ownership.
   The ASF licenses this file to you under the Apache License, Version 2.0.
 -->
 <!doctype html>
 <html lang="en">
 <head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1"><meta name="description" content="IVF-RQ multi-bit rotated residual codes, two-stage distance estimation, tuning, benchmarks, and v1 storage layout."><title>IVF-RQ · Paimon Vector Index</title><link rel="stylesheet" href="styles.css"><script src="docs.js" defer></script></head>
 <body>
   <a class="skip-link" href="#main">Skip to content</a>
   <header class="site-header"><div class="header-inner"><a class="brand" href="index.html" aria-label="Paimon Vector Index documentation home"><span class="brand-mark">VI</span><span>Paimon Vector Index</span></a><nav class="site-nav" data-site-nav aria-label="Documentation"><a href="index.html">Overview</a><a href="api.html">API</a><a href="development.html">Development</a><a href="ivf-flat.html">IVF-FLAT</a><a href="ivf-pq.html">IVF-PQ</a><a href="ivf-rq.html" aria-current="page">IVF-RQ</a><a href="ivf-sq.html">IVF-SQ</a><a href="diskann.html">DiskANN</a><a href="releases.html">Releases</a></nav><div class="header-actions"><button class="icon-button" type="button" data-theme-toggle aria-label="Switch color theme">◐</button><button class="nav-toggle" type="button" data-nav-toggle aria-expanded="false" aria-label="Open navigation">☰</button></div></div></header>
   <main id="main"><div class="page-shell">
     <section class="hero detail-hero"><p class="eyebrow">Multi-bit rotated residual quantization</p><h1>IVF-RQ</h1><p class="hero-lead">Partition vectors with IVF, spread each residual through a deterministic orthogonal transform, and store centered scalar levels as bit planes. A cheap sign-plane estimate rejects weak candidates before the remaining planes are evaluated.</p><div class="badge-row"><span class="badge strong">4 bits / dimension by default</span><span class="badge">1–8 build-time bits</span><span class="badge">two-stage scan</span><span class="badge">Magic: IVRQ</span></div></section>
     <div class="doc-layout">
       <aside class="toc" aria-label="On this page"><strong>On this page</strong><a href="#position">Positioning</a><a href="#design">Design</a><a href="#usage">Usage</a><a href="#parameters">Parameters</a><a href="#benchmarks">Benchmarks</a><a href="#storage">Storage layout</a><a href="#sizing">Capacity</a><a href="#tuning">Tuning</a><a href="#limits">Boundaries</a></aside>
       <article class="article">
         <section class="article-section" id="position">
           <h2>Positioning and trade-offs</h2>
           <div class="metric-strip"><div class="metric"><span class="label">Default code</span><span class="value"><code>padded_d / 2</code> bytes</span></div><div class="metric"><span class="label">Per-vector factors</span><span class="value">5 × <code>f32</code></span></div><div class="metric"><span class="label">Learned model</span><span class="value">IVF centroids only</span></div><div class="metric"><span class="label">Dimension</span><span class="value">Any positive value</span></div></div>
           <div class="split"><div class="pro-con"><h3>Good fit</h3><ul><li>You need higher recall than IVF-SQ at a smaller serialized size.</li><li>Training time and model complexity should stay close to IVF-FLAT.</li><li>The source supports one concurrent multi-range read for selected lists.</li><li>Approximate in-list ranking is acceptable and measured against real ground truth.</li></ul></div><div class="pro-con"><h3>Poor fit</h3><ul><li>Raw-vector or exact reranking accuracy is mandatory.</li><li>Sub-millisecond local latency matters more than 0.90-class recall.</li><li>The collection is highly mutable; this implementation writes immutable files.</li><li>Resident PQ tables and lower recall are acceptable in exchange for a still smaller IVF-PQ index.</li></ul></div></div>
           <div class="callout"><strong>Why it remains IVF-RQ</strong>The public index family name is unchanged. The pre-release 1-bit/query-bit experiment was replaced completely: bit width is now a property of persisted data, not a per-query switch.</div>
         </section>

         <section class="article-section" id="design">
           <h2>Design and distance estimation</h2>
           <div class="pipeline"><div class="pipeline-item"><span class="pipeline-index">1</span><div><h3>Train and assign IVF</h3><p>Learn <code>nlist</code> coarse centroids and form <code>r = x − c</code>.</p></div></div><div class="pipeline-item"><span class="pipeline-index">2</span><div><h3>Rotate deterministically</h3><p>Pad to a multiple of 64, then apply four rounds of random signs, 64-wide normalized FHT, and seeded permutation. The transform is orthogonal and reconstructed from the header seed.</p></div></div><div class="pipeline-item"><span class="pipeline-index">3</span><div><h3>Quantize centered levels</h3><p>Choose 1–8 bits and refine one per-vector scale for three rounds. Store levels MSB first as bit planes.</p></div></div><div class="pipeline-item"><span class="pipeline-index">4</span><div><h3>Estimate in two stages</h3><p>The MSB sign plane and its three factors produce an estimate plus a deterministic reconstruction-error bound. Only candidates whose lower bound can enter Top-K evaluate all planes and the full factors.</p></div></div><div class="pipeline-item"><span class="pipeline-index">5</span><div><h3>Scan blocked data</h3><p>Codes and factors are transposed within 32-vector blocks. The rotated query and byte LUT are built once and reused across every selected list.</p></div></div></div>
           <p>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.</p>
         </section>

         <section class="article-section" id="usage">
           <h2>Usage</h2>
           <div class="code-block"><span class="code-label">Java · build and query</span><pre><code>Map&lt;String, String&gt; options = new HashMap&lt;&gt;();
 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");

 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();
 }</code></pre></div>
           <div class="code-block"><span class="code-label">Rust · configuration</span><pre><code>let config = VectorIndexConfig::IvfRq {
     dimension: 128,
     nlist: 1024,
     bits: 4,
     metric: MetricType::L2,
 };
 let params = VectorSearchParams::new(10, 64);</code></pre></div>
         </section>

         <section class="article-section" id="parameters">
           <h2>Parameters</h2>
           <div class="table-wrap"><table><thead><tr><th>Parameter</th><th>Requirement / default</th><th>Purpose</th><th>Guidance</th></tr></thead><tbody><tr><td><code>dimension</code></td><td>Inferred by Java/Python one-shot training; otherwise &gt; 0</td><td>Logical vector dimension</td><td>Storage pads internally to a multiple of 64.</td></tr><tr><td><code>nlist</code></td><td>Auto from <code>expected-vector-count</code>, or explicit &gt; 0</td><td>IVF partition count</td><td>Compare the resolved value with the same IVF-FLAT baseline.</td></tr><tr><td><code>rq.bits</code></td><td>1–8; auto from <code>max-bytes-per-vector</code>, otherwise 4</td><td>Persisted residual level width</td><td>Higher values increase recall, file bytes, I/O, and scan work linearly.</td></tr><tr><td><code>metric</code></td><td>Required</td><td>L2 / inner product / cosine</td><td>Semantic, not inferred; fixed in the file.</td></tr><tr><td><code>nprobe</code></td><td>Automatic by default; explicit expert override</td><td>Lists probed</td><td>Auto accounts for K, average list size, and filter selectivity.</td></tr></tbody></table></div>
           <div class="callout warning"><strong>No query-side bit width</strong>The Reader always evaluates the representation stored in the file. Changing <code>rq.bits</code> requires rebuilding the index; this keeps one file's accuracy and cost contract stable.</div>
         </section>

         <section class="article-section" id="benchmarks">
           <h2>Public-corpus measurements</h2>
           <p>Apple M4 Pro, 12 Rayon workers, one million base vectors, 1,000 published queries, <code>nlist=1024</code>, <code>nprobe=64</code>, Top-10, warm APFS pages. Times are release-build measurements from 25 July 2026.</p>
           <div class="table-wrap"><table><thead><tr><th>Dataset</th><th>Build</th><th>File</th><th>Recall@10</th><th>Local P95</th><th>Local batch QPS</th><th>Read / query</th></tr></thead><tbody><tr><td>SIFT1M, 128d</td><td>3.92 s</td><td>86.3 MB</td><td>0.9148</td><td>1.20 ms</td><td>3,074</td><td>5.81 MB</td></tr><tr><td>GIST1M, 960d</td><td>23.5 s</td><td>505.8 MB</td><td>0.9039</td><td>4.41 ms</td><td>444</td><td>38.81 MB</td></tr><tr><td>GloVe-100, 100d</td><td>4.03 s</td><td>102.1 MB</td><td>0.8203</td><td>1.23 ms</td><td>2,917</td><td>6.18 MB</td></tr></tbody></table></div>
           <p>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.</p>
           <div class="table-wrap"><table><thead><tr><th>GIST1M storage model</th><th>Recall@10</th><th>P95</th><th>Batch QPS</th><th>Query rounds</th></tr></thead><tbody><tr><td>Warm local storage</td><td>0.9039</td><td>4.41 ms</td><td>444</td><td>1</td></tr><tr><td>Remote cache, fixed 2 ms</td><td>0.9039</td><td>7.80 ms</td><td>434</td><td>1</td></tr><tr><td>Object store, fixed 20 ms</td><td>0.9039</td><td>24.34 ms</td><td>392</td><td>1</td></tr></tbody></table></div>
           <div class="callout"><strong>What changed in this run</strong>Rows are assigned to IVF lists once, then independent lists are encoded in parallel with task-local residual, rotation, code, and factor scratch. The unfiltered scan removes the per-lane filter test from coarse-code accumulation, and the final estimator checks the Top-K threshold before entering the duplicate-aware heap. Relative to the immediately preceding same-machine build, add time fell 39% / 45% / 42% on SIFT/GIST/GloVe; a strict GIST same-file query A/B improved batch time by 8.7%. Rebuilt file hashes match the serial baseline exactly, so these are execution-path changes rather than a format or estimator change.</div>
           <p>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.</p>
         </section>

         <section class="article-section" id="storage">
           <h2>v1 storage layout</h2>
           <div class="storage-map" aria-label="IVF-RQ file layout"><div class="storage-block primary"><strong>64 B header</strong>Shape, bits, transform, layout</div><div class="storage-block"><strong>IVF centers</strong><code>nlist × d × f32</code></div><div class="storage-block"><strong>Offset table</strong><code>nlist × 16 B</code></div><div class="storage-block"><strong>Lists</strong>IDs + blocked planes + blocked factors</div></div>
           <p>The header records logical and padded dimensions, metric, required layout flags, persisted <code>rq.bits</code>, total vectors, rotation seed/rounds, plane bytes, rotation type 2, and compact factor layout 3. Every non-empty list begins with <code>base_id</code>, encoded-ID length, and code length, followed by sorted delta-varint IDs.</p>
           <p>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 <code>(f_add, f_rescale, f_error)</code> followed by full <code>(f_add, f_rescale)</code>. 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.</p>
           <div class="callout"><strong>Open-source cross-check</strong><a href="https://github.com/facebookresearch/faiss/blob/main/faiss/IndexIVFRaBitQFastScan.h">Faiss IVFRaBitQ FastScan</a> also groups database vectors in 32-lane blocks and separates RaBitQ correction factors from packed codes. <a href="https://github.com/lancedb/lance/blob/main/rust/lance-index/src/vector/bq/ex_dot.rs">Lance's RaBitQ kernels</a> likewise use blocked multi-bit codes and architecture-specific dot products. The v1 plane/byte/lane layout and SoA factors already preserve the important scan locality, while sorted delta-varint row IDs avoid fixed-width ID overhead. A quantized-LUT SIMD port remains future work because its rounding error must be incorporated into the conservative first-stage bound; the current release keeps exact F32 table sums.</div>
           <div class="callout"><strong>Why the remaining factors stay F32</strong><a href="https://github.com/facebookresearch/faiss/wiki/Additive-quantizers">Faiss additive quantizers</a> can encode norms with qint8 or qint4. IVF-RQ cannot apply that choice blindly to its coarse factors: their error term makes the first-stage lower bound conservative, and inward rounding could incorrectly prune a true Top-K candidate. v1 takes the lossless 4-byte saving by deleting only the unused final-stage error; lower-precision factor encodings remain gated on a proof-preserving rounding rule and public-corpus recall data.</div>
           <div class="callout"><strong>I/O contract</strong>Open reads the 64-byte header once. Resident initialization reads centroids plus the offset table in one contiguous round. Search groups selected list payloads into at most 64 MiB per round and also honors <code>SeekReadCapabilities.max_ranges_per_pread</code>. Each returned payload remains the backing allocation for its blocked codes, so the reader decodes only IDs and factors instead of copying the usually much larger code region.</div>
         </section>

         <section class="article-section" id="sizing">
           <h2>Capacity estimate</h2>
           <div class="callout"><strong>Approximate default size</strong><code>64 + 4×nlist×d + 16×nlist + N×(4×padded_d/8 + 20) + encoded_ids</code></div>
           <p>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.</p>
         </section>

         <section class="article-section" id="tuning">
           <h2>Tuning order</h2>
           <ol><li>Run IVF-FLAT with the target <code>nlist/nprobe</code> to establish the partition recall ceiling.</li><li>Start IVF-RQ at the default four bits.</li><li>If recall is low for both indexes, increase <code>nprobe</code>. If only IVF-RQ is low, try five bits before increasing I/O through more lists.</li><li>Compare IVF-SQ when simpler/faster scans matter; compare IVF-PQ when minimum size matters.</li><li>Validate the final choice on a public or production corpus, including batch and the real storage adapter.</li></ol>
         </section>

         <section class="article-section" id="limits">
           <h2>Implementation boundaries</h2>
           <ul><li>The file is immutable; updates require a new index file.</li><li>Distances are approximate and raw vectors are not retained for exact reranking.</li><li>Four transform rounds and compact factor layout 3 are fixed for v1; readers reject other values.</li><li>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.</li><li><code>optimize_for_search()</code> loads and validates resident metadata; it does not change search results.</li></ul>
           <nav class="pager" aria-label="Index navigation"><a href="ivf-pq.html"><small>Previous</small>← IVF-PQ</a><a href="ivf-sq.html"><small>Next</small>IVF-SQ →</a></nav>
         </section>
       </article>
     </div>
   </div></main>
   <footer class="site-footer"><div class="footer-inner"><span>Apache Paimon Vector Index</span><span>IVF-RQ · v1</span></div></footer>
 </body>
 </html>
	<!--
	Licensed to the Apache Software Foundation (ASF) under one or more
	contributor license agreements. See the NOTICE file distributed with
	this work for additional information regarding copyright ownership.
	The ASF licenses this file to you under the Apache License, Version 2.0.
	-->
	<!doctype html>
	<html lang="en">
	<head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1"><meta name="description" content="IVF-RQ multi-bit rotated residual codes, two-stage distance estimation, tuning, benchmarks, and v1 storage layout."><title>IVF-RQ · Paimon Vector Index</title><link rel="stylesheet" href="styles.css"><script src="docs.js" defer></script></head>
	<body>
	<a class="skip-link" href="#main">Skip to content</a>
	<header class="site-header"><div class="header-inner"><a class="brand" href="index.html" aria-label="Paimon Vector Index documentation home"><span class="brand-mark">VI</span><span>Paimon Vector Index</span></a><nav class="site-nav" data-site-nav aria-label="Documentation"><a href="index.html">Overview</a><a href="api.html">API</a><a href="development.html">Development</a><a href="ivf-flat.html">IVF-FLAT</a><a href="ivf-pq.html">IVF-PQ</a><a href="ivf-rq.html" aria-current="page">IVF-RQ</a><a href="ivf-sq.html">IVF-SQ</a><a href="diskann.html">DiskANN</a><a href="releases.html">Releases</a></nav><div class="header-actions"><button class="icon-button" type="button" data-theme-toggle aria-label="Switch color theme">◐</button><button class="nav-toggle" type="button" data-nav-toggle aria-expanded="false" aria-label="Open navigation">☰</button></div></div></header>
	<main id="main"><div class="page-shell">
	<section class="hero detail-hero"><p class="eyebrow">Multi-bit rotated residual quantization</p><h1>IVF-RQ</h1><p class="hero-lead">Partition vectors with IVF, spread each residual through a deterministic orthogonal transform, and store centered scalar levels as bit planes. A cheap sign-plane estimate rejects weak candidates before the remaining planes are evaluated.</p><div class="badge-row"><span class="badge strong">4 bits / dimension by default</span><span class="badge">1–8 build-time bits</span><span class="badge">two-stage scan</span><span class="badge">Magic: IVRQ</span></div></section>
	<div class="doc-layout">
	<aside class="toc" aria-label="On this page"><strong>On this page</strong><a href="#position">Positioning</a><a href="#design">Design</a><a href="#usage">Usage</a><a href="#parameters">Parameters</a><a href="#benchmarks">Benchmarks</a><a href="#storage">Storage layout</a><a href="#sizing">Capacity</a><a href="#tuning">Tuning</a><a href="#limits">Boundaries</a></aside>
	<article class="article">
	<section class="article-section" id="position">
	<h2>Positioning and trade-offs</h2>
	<div class="metric-strip"><div class="metric"><span class="label">Default code</span><span class="value"><code>padded_d / 2</code> bytes</span></div><div class="metric"><span class="label">Per-vector factors</span><span class="value">5 × <code>f32</code></span></div><div class="metric"><span class="label">Learned model</span><span class="value">IVF centroids only</span></div><div class="metric"><span class="label">Dimension</span><span class="value">Any positive value</span></div></div>
	<div class="split"><div class="pro-con"><h3>Good fit</h3><ul><li>You need higher recall than IVF-SQ at a smaller serialized size.</li><li>Training time and model complexity should stay close to IVF-FLAT.</li><li>The source supports one concurrent multi-range read for selected lists.</li><li>Approximate in-list ranking is acceptable and measured against real ground truth.</li></ul></div><div class="pro-con"><h3>Poor fit</h3><ul><li>Raw-vector or exact reranking accuracy is mandatory.</li><li>Sub-millisecond local latency matters more than 0.90-class recall.</li><li>The collection is highly mutable; this implementation writes immutable files.</li><li>Resident PQ tables and lower recall are acceptable in exchange for a still smaller IVF-PQ index.</li></ul></div></div>
	<div class="callout"><strong>Why it remains IVF-RQ</strong>The public index family name is unchanged. The pre-release 1-bit/query-bit experiment was replaced completely: bit width is now a property of persisted data, not a per-query switch.</div>
	</section>

	<section class="article-section" id="design">
	<h2>Design and distance estimation</h2>
	<div class="pipeline"><div class="pipeline-item"><span class="pipeline-index">1</span><div><h3>Train and assign IVF</h3><p>Learn <code>nlist</code> coarse centroids and form <code>r = x − c</code>.</p></div></div><div class="pipeline-item"><span class="pipeline-index">2</span><div><h3>Rotate deterministically</h3><p>Pad to a multiple of 64, then apply four rounds of random signs, 64-wide normalized FHT, and seeded permutation. The transform is orthogonal and reconstructed from the header seed.</p></div></div><div class="pipeline-item"><span class="pipeline-index">3</span><div><h3>Quantize centered levels</h3><p>Choose 1–8 bits and refine one per-vector scale for three rounds. Store levels MSB first as bit planes.</p></div></div><div class="pipeline-item"><span class="pipeline-index">4</span><div><h3>Estimate in two stages</h3><p>The MSB sign plane and its three factors produce an estimate plus a deterministic reconstruction-error bound. Only candidates whose lower bound can enter Top-K evaluate all planes and the full factors.</p></div></div><div class="pipeline-item"><span class="pipeline-index">5</span><div><h3>Scan blocked data</h3><p>Codes and factors are transposed within 32-vector blocks. The rotated query and byte LUT are built once and reused across every selected list.</p></div></div></div>
	<p>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.</p>
	</section>

	<section class="article-section" id="usage">
	<h2>Usage</h2>
	<div class="code-block"><span class="code-label">Java · build and query</span><pre><code>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");

	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();
	}</code></pre></div>
	<div class="code-block"><span class="code-label">Rust · configuration</span><pre><code>let config = VectorIndexConfig::IvfRq {
	dimension: 128,
	nlist: 1024,
	bits: 4,
	metric: MetricType::L2,
	};
	let params = VectorSearchParams::new(10, 64);</code></pre></div>
	</section>

	<section class="article-section" id="parameters">
	<h2>Parameters</h2>
	<div class="table-wrap"><table><thead><tr><th>Parameter</th><th>Requirement / default</th><th>Purpose</th><th>Guidance</th></tr></thead><tbody><tr><td><code>dimension</code></td><td>Inferred by Java/Python one-shot training; otherwise > 0</td><td>Logical vector dimension</td><td>Storage pads internally to a multiple of 64.</td></tr><tr><td><code>nlist</code></td><td>Auto from <code>expected-vector-count</code>, or explicit > 0</td><td>IVF partition count</td><td>Compare the resolved value with the same IVF-FLAT baseline.</td></tr><tr><td><code>rq.bits</code></td><td>1–8; auto from <code>max-bytes-per-vector</code>, otherwise 4</td><td>Persisted residual level width</td><td>Higher values increase recall, file bytes, I/O, and scan work linearly.</td></tr><tr><td><code>metric</code></td><td>Required</td><td>L2 / inner product / cosine</td><td>Semantic, not inferred; fixed in the file.</td></tr><tr><td><code>nprobe</code></td><td>Automatic by default; explicit expert override</td><td>Lists probed</td><td>Auto accounts for K, average list size, and filter selectivity.</td></tr></tbody></table></div>
	<div class="callout warning"><strong>No query-side bit width</strong>The Reader always evaluates the representation stored in the file. Changing <code>rq.bits</code> requires rebuilding the index; this keeps one file's accuracy and cost contract stable.</div>
	</section>

	<section class="article-section" id="benchmarks">
	<h2>Public-corpus measurements</h2>
	<p>Apple M4 Pro, 12 Rayon workers, one million base vectors, 1,000 published queries, <code>nlist=1024</code>, <code>nprobe=64</code>, Top-10, warm APFS pages. Times are release-build measurements from 25 July 2026.</p>
	<div class="table-wrap"><table><thead><tr><th>Dataset</th><th>Build</th><th>File</th><th>Recall@10</th><th>Local P95</th><th>Local batch QPS</th><th>Read / query</th></tr></thead><tbody><tr><td>SIFT1M, 128d</td><td>3.92 s</td><td>86.3 MB</td><td>0.9148</td><td>1.20 ms</td><td>3,074</td><td>5.81 MB</td></tr><tr><td>GIST1M, 960d</td><td>23.5 s</td><td>505.8 MB</td><td>0.9039</td><td>4.41 ms</td><td>444</td><td>38.81 MB</td></tr><tr><td>GloVe-100, 100d</td><td>4.03 s</td><td>102.1 MB</td><td>0.8203</td><td>1.23 ms</td><td>2,917</td><td>6.18 MB</td></tr></tbody></table></div>
	<p>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.</p>
	<div class="table-wrap"><table><thead><tr><th>GIST1M storage model</th><th>Recall@10</th><th>P95</th><th>Batch QPS</th><th>Query rounds</th></tr></thead><tbody><tr><td>Warm local storage</td><td>0.9039</td><td>4.41 ms</td><td>444</td><td>1</td></tr><tr><td>Remote cache, fixed 2 ms</td><td>0.9039</td><td>7.80 ms</td><td>434</td><td>1</td></tr><tr><td>Object store, fixed 20 ms</td><td>0.9039</td><td>24.34 ms</td><td>392</td><td>1</td></tr></tbody></table></div>
	<div class="callout"><strong>What changed in this run</strong>Rows are assigned to IVF lists once, then independent lists are encoded in parallel with task-local residual, rotation, code, and factor scratch. The unfiltered scan removes the per-lane filter test from coarse-code accumulation, and the final estimator checks the Top-K threshold before entering the duplicate-aware heap. Relative to the immediately preceding same-machine build, add time fell 39% / 45% / 42% on SIFT/GIST/GloVe; a strict GIST same-file query A/B improved batch time by 8.7%. Rebuilt file hashes match the serial baseline exactly, so these are execution-path changes rather than a format or estimator change.</div>
	<p>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.</p>
	</section>

	<section class="article-section" id="storage">
	<h2>v1 storage layout</h2>
	<div class="storage-map" aria-label="IVF-RQ file layout"><div class="storage-block primary"><strong>64 B header</strong>Shape, bits, transform, layout</div><div class="storage-block"><strong>IVF centers</strong><code>nlist × d × f32</code></div><div class="storage-block"><strong>Offset table</strong><code>nlist × 16 B</code></div><div class="storage-block"><strong>Lists</strong>IDs + blocked planes + blocked factors</div></div>
	<p>The header records logical and padded dimensions, metric, required layout flags, persisted <code>rq.bits</code>, total vectors, rotation seed/rounds, plane bytes, rotation type 2, and compact factor layout 3. Every non-empty list begins with <code>base_id</code>, encoded-ID length, and code length, followed by sorted delta-varint IDs.</p>
	<p>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 <code>(f_add, f_rescale, f_error)</code> followed by full <code>(f_add, f_rescale)</code>. 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.</p>
	<div class="callout"><strong>Open-source cross-check</strong><a href="https://github.com/facebookresearch/faiss/blob/main/faiss/IndexIVFRaBitQFastScan.h">Faiss IVFRaBitQ FastScan</a> also groups database vectors in 32-lane blocks and separates RaBitQ correction factors from packed codes. <a href="https://github.com/lancedb/lance/blob/main/rust/lance-index/src/vector/bq/ex_dot.rs">Lance's RaBitQ kernels</a> likewise use blocked multi-bit codes and architecture-specific dot products. The v1 plane/byte/lane layout and SoA factors already preserve the important scan locality, while sorted delta-varint row IDs avoid fixed-width ID overhead. A quantized-LUT SIMD port remains future work because its rounding error must be incorporated into the conservative first-stage bound; the current release keeps exact F32 table sums.</div>
	<div class="callout"><strong>Why the remaining factors stay F32</strong><a href="https://github.com/facebookresearch/faiss/wiki/Additive-quantizers">Faiss additive quantizers</a> can encode norms with qint8 or qint4. IVF-RQ cannot apply that choice blindly to its coarse factors: their error term makes the first-stage lower bound conservative, and inward rounding could incorrectly prune a true Top-K candidate. v1 takes the lossless 4-byte saving by deleting only the unused final-stage error; lower-precision factor encodings remain gated on a proof-preserving rounding rule and public-corpus recall data.</div>
	<div class="callout"><strong>I/O contract</strong>Open reads the 64-byte header once. Resident initialization reads centroids plus the offset table in one contiguous round. Search groups selected list payloads into at most 64 MiB per round and also honors <code>SeekReadCapabilities.max_ranges_per_pread</code>. Each returned payload remains the backing allocation for its blocked codes, so the reader decodes only IDs and factors instead of copying the usually much larger code region.</div>
	</section>

	<section class="article-section" id="sizing">
	<h2>Capacity estimate</h2>
	<div class="callout"><strong>Approximate default size</strong><code>64 + 4×nlist×d + 16×nlist + N×(4×padded_d/8 + 20) + encoded_ids</code></div>
	<p>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.</p>
	</section>

	<section class="article-section" id="tuning">
	<h2>Tuning order</h2>
	<ol><li>Run IVF-FLAT with the target <code>nlist/nprobe</code> to establish the partition recall ceiling.</li><li>Start IVF-RQ at the default four bits.</li><li>If recall is low for both indexes, increase <code>nprobe</code>. If only IVF-RQ is low, try five bits before increasing I/O through more lists.</li><li>Compare IVF-SQ when simpler/faster scans matter; compare IVF-PQ when minimum size matters.</li><li>Validate the final choice on a public or production corpus, including batch and the real storage adapter.</li></ol>
	</section>

	<section class="article-section" id="limits">
	<h2>Implementation boundaries</h2>
	<ul><li>The file is immutable; updates require a new index file.</li><li>Distances are approximate and raw vectors are not retained for exact reranking.</li><li>Four transform rounds and compact factor layout 3 are fixed for v1; readers reject other values.</li><li>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.</li><li><code>optimize_for_search()</code> loads and validates resident metadata; it does not change search results.</li></ul>
	<nav class="pager" aria-label="Index navigation"><a href="ivf-pq.html"><small>Previous</small>← IVF-PQ</a><a href="ivf-sq.html"><small>Next</small>IVF-SQ →</a></nav>
	</section>
	</article>
	</div>
	</div></main>
	<footer class="site-footer"><div class="footer-inner"><span>Apache Paimon Vector Index</span><span>IVF-RQ · v1</span></div></footer>
	</body>
	</html>