Vector Index

Relevant source files

• src/superfile/reader.rs
• src/superfile/vector/builder.rs
• src/superfile/vector/distance.rs
• src/superfile/vector/mod.rs
• src/superfile/vector/quant.rs
• src/superfile/vector/reader.rs
• src/superfile/vector/rerank_codec.rs
• src/superfile/vector/reservoir.rs
• src/superfile/vector/rotation.rs
• src/superfile/vector/simd_dispatch.rs
• src/superfile/vector/spill.rs
• src/superfile/vector/sq8_simd.rs
• src/supertable/manifest/bloom.rs
• tests/superfile/vector/reservoir_recall.rs

The vector index subsystem provides high-performance approximate nearest neighbor (ANN) search within a superfile. It utilizes an IVF (Inverted File Index) structure combined with RaBitQ (Random Bilinear Quantization) for fast shortlisting and various Rerank Codecs (including SQ8 and FP32) for final precision.

Architecture & Data Flow

The vector subsystem is designed for object-storage-native performance, prioritizing sequential access and SIMD-accelerated distance kernels.

Build Pipeline

The VectorBuilder implements a three-pass streaming pipeline to construct the index while keeping memory consumption bounded:

1. Pass 1: Training & Reservoir Sampling: A Reservoir uses Vitter's Algorithm L to collect a representative sample of the corpus src/superfile/vector/reservoir.rs18-33 Lloyd's k-means then trains IVF centroids on this sample src/superfile/vector/builder.rs69-72
2. Pass 2: Rotation & Spilling: Every input vector is transformed via a RandomRotation (3-stage Walsh-Hadamard Transform) src/superfile/vector/rotation.rs19-28 Vectors are assigned to the nearest centroid and "spilled" to disk-backed buckets via SpillWriter src/superfile/vector/builder.rs41-43
3. Pass 3: Quantization & Finishing: Each cluster bucket is read. Vectors are quantized into 1-bit RaBitQ codes and rerank bytes (SQ8 or FP32) and written to the final unified blob src/superfile/vector/builder.rs7-12

Search Pipeline

The VectorReader executes queries in three stages:

1. IVF Probe: Distance is calculated between the query and all centroids to find the top nprobe clusters.
2. RaBitQ Shortlist: For each probed cluster, the reader performs a SIMD-accelerated dot product estimate using 1-bit codes via BitQuantizer::estimate_dot_rotated_with_total src/superfile/vector/quant.rs152-161
3. Refine/Rerank: The top candidates from the shortlist are re-scored using higher-precision rerank bytes (e.g., SQ8 or FP32) to produce the final top-k src/superfile/vector/reader.rs4-5

Vector Search Entity Map

This diagram associates high-level search concepts with the specific Rust entities implementing them.

Sources: src/superfile/vector/reader.rs4-12 src/superfile/vector/distance.rs10-13 src/superfile/vector/quant.rs4-10 src/superfile/vector/rerank_codec.rs4-17

---

IVF Clustering & Reservoir Sampling

To avoid loading the entire corpus into memory during index construction, Infino uses Reservoir Sampling.

Reservoir Sampling (Reservoir)

The Reservoir maintains a fixed-size uniform random sample of vectors src/superfile/vector/reservoir.rs8-14

• Default Size: max(100K, min(500K, 64 × n_cent)) src/superfile/vector/reservoir.rs70-80
• Algorithm: Vitter's Algorithm L, which reduces the number of random draws as the stream grows src/superfile/vector/reservoir.rs18-23

k-means Training

Centroids are trained using Lloyd's k-means on the reservoir sample src/superfile/vector/builder.rs69-72 The number of centroids (n_cent) is capped based on the total document count to prevent over-partitioning small files src/superfile/vector/builder.rs115-123

Sources: src/superfile/vector/reservoir.rs50-115 src/superfile/vector/builder.rs86-98 src/superfile/vector/kmeans.rs4-12

---

Rotation & Quantization

Fast Structured Rotation (RandomRotation)

1-bit quantization requires spreading data variance. Infino uses a Structured Spinner construction src/superfile/vector/rotation.rs12-21:

• Components: 3 stages of (Random Sign Flip + Walsh-Hadamard Transform) src/superfile/vector/rotation.rs49-53
• Complexity: $O(d \log d)$ per vector, significantly faster than $O(d^2)$ dense matrix multiplication src/superfile/vector/rotation.rs13-15

RaBitQ Quantization (BitQuantizer)

Rotated vectors are compressed to 1 bit per dimension (sign bit) src/superfile/vector/quant.rs6-7

• Estimation: The dot product is estimated via a SIMD-friendly identity: $dot = 2 \cdot pos_sum - q_total$ src/superfile/vector/quant.rs19-22
• SIMD Optimization: On AVX-512 hosts, this uses _mm512_mask_add_ps to sum query lanes keyed by the document's bit pattern src/superfile/vector/quant.rs23-28

Sources: src/superfile/vector/rotation.rs4-41 src/superfile/vector/quant.rs4-38

---

Rerank Codecs & SIMD Kernels

After the RaBitQ shortlist, a refine pass uses a RerankCodec to calculate precise distances.

Codec	Storage (per dim)	Description
Fp32	4 bytes	Bit-exact precision, zero-copy SIMD src/superfile/vector/rerank_codec.rs8-9
Sq8ResidualEpsilon	2 bytes	Default. SQ8 codes + signed 8-bit residual sidecar src/superfile/vector/rerank_codec.rs10-14
RabitqOnly	0 bytes	Skips reranking; uses shortlist as final ranking src/superfile/vector/rerank_codec.rs15-17

SQ8 SIMD Kernels (sq8_simd.rs)

The SQ8 codec utilizes specialized kernels for quantization:

• Min/Max Update: Tracks per-dimension value ranges during spilling via update_min_max src/superfile/vector/sq8_simd.rs9-11
• Encode: Uses FMA (Fused Multiply-Add) to map floats to [0, 255] with round-half-up bias: $q = x \cdot inv_scale + c2$ src/superfile/vector/sq8_simd.rs62-67

Distance Kernels (distance.rs)

Infino supports three metrics, all optimized with AVX-512 and AVX2/NEON (via wide) dispatch src/superfile/vector/distance.rs4-13:

• Cosine: 1.0 - dot(a, b) (assumes unit vectors) src/superfile/vector/distance.rs62-64
• L2Sq: Squared Euclidean distance $\sum (a-b)^2$ src/superfile/vector/distance.rs65-66
• NegDot: Maximum Inner Product Search (MIPS) via negated dot product src/superfile/vector/distance.rs67-69

Sources: src/superfile/vector/rerank_codec.rs4-21 src/superfile/vector/sq8_simd.rs4-31 src/superfile/vector/distance.rs4-81

---

On-Disk Layout

The vector index is stored as a unified blob within the superfile, divided into per-column subsections.

Subsection Structure

Each column's data is cluster-contiguous to ensure range-GET efficiency src/superfile/vector/builder.rs7-10

Region	Content
Sub-Header	Metadata (dim, n_cent, metric, offsets) src/superfile/vector/reader.rs124-140
Centroids	Raw fp32 IVF centroids.
Cluster Index	Offsets and counts for each cluster's data block src/superfile/vector/reader.rs129-130
Codec Meta	Auxiliary data for quantizers (e.g., SQ8 scales/offsets) src/superfile/vector/rerank_codec.rs32-35
Per-Cluster Blocks	Interleaved [RaBitQ Codes][Doc IDs][Rerank Vectors] src/superfile/vector/reader.rs141-149

Unified Blob Entity Map

This diagram shows how the VectorBuilder assembles the on-disk format and how VectorReader parses it.

Sources: src/superfile/vector/builder.rs4-12 src/superfile/vector/reader.rs102-157 src/superfile/vector/reader.rs180-190