How Turbovec Vectors Are Bit-Packed for Compression

Turbovec reduces memory usage by quantizing f32 dimensions to 2-4 bit integer codes, arranging these into separate bit-planes, and reorganizing them into 32-vector SIMD blocks that maximize dot-product throughput during search.

The RyanCodrai/turbovec repository implements a specialized compression pipeline that transforms high-dimensional floating-point vectors into a bit-packed representation. This scheme shrinks storage requirements from 4 bytes per dimension to less than 0.5 bytes while maintaining a data layout optimized for SIMD instruction sets.

The Three-Stage Bit-Packing Pipeline

The compression logic in turbovec/src/pack.rs processes vectors through three distinct transformations, converting raw floating-point data into the native blocked layout consumed by search kernels.

Stage 1: Bit-Plane Packing and Quantization

The process begins with quantization, where each dimension of a vector is reduced to a small integer code using 2, 3, or 4 bits. These bits are arranged into bit-planes—separate arrays where all 0-bits are stored contiguously, followed by all 1-bits, and so on.

A vector of dimension dim (which must be a multiple of 8) generates bits × (dim / 8) bytes in this layout. The entry point repack (lines 59-73) receives already-packed bytes and initiates the extraction process by forwarding data to the flat extraction routine.

// Entry point in turbovec/src/pack.rs (lines 59-73)
pub fn repack(packed_codes: &[u8], n_vectors: usize, bits: usize, dim: usize) 
    -> (Vec<u8>, usize) {
    let codes_flat = extract_codes_flat(packed_codes, n_vectors, bits, dim);
    // ... proceeds to SIMD blocking
}

Stage 2: Flat Extraction with LUT Optimization

The bit-plane representation transforms into a flat row-major buffer (codes_flat) where each row corresponds to a vector and each column represents a byte-group (a collection of dim / codes_per_byte bytes). This conversion avoids expensive per-bit loops by utilizing pre-computed lookup tables.

The extract_codes_flat function (lines 303-334) performs this transformation using the EXTRACT_LUTS constant, which is generated by build_extract_lut (lines 64-81). The helper extract_lut (lines 94-96) selects the appropriate table based on bit width, allowing the extraction to proceed via table lookups rather than bit manipulation.

// Flat extraction using LUTs (conceptual)
let lut = extract_lut(bits); // lines 94-96
// EXTRACT_LUTS provides O(1) bit extraction per plane byte

Stage 3: SIMD-Blocked Re-Packing

The final stage reorganizes the flat buffer into 32-vector blocks optimized for SIMD dot-product instructions. The layout diverges based on target architecture:

• Non-x86 targets: Uses pack_blocked_sequential (lines 350-361) to arrange vectors sequentially within each block.
• x86-64: Employs the pack_blocked_native! macro (lines 19-46) to apply FAISS-style nibble interleaving using the PERM0 permutation via pack_blocked (lines 76-102).

On x86, the macro may also invoke vector_major8_chunk or vector_major_chunk for vector-major layouts. The function returns a tuple (blocked, n_blocks) where blocked contains the SIMD-ready bytes and n_blocks indicates the count of 32-vector blocks.

Platform-Specific Layout Transformations

The native layout differs significantly between architectures. On non-x86 systems, vectors remain in sequential order within blocks. However, on x86-64, the FAISS-style interleaving rearranges nibbles to align with vpdpbusd and sdot instruction patterns.

When loading pre-packed indices from disk, apply_native_transform performs the x86-specific interleaving in-place, avoiding a full repack operation. This optimization ensures that serialization uses the portable sequential format while runtime search uses the high-performance native layout.

Memory Layout Specifications

The bit-packing scheme maintains three distinct memory representations:

• Bit-plane layout: Separates bits by significance (all bit-0, then all bit-1, etc.) for efficient LUT-based extraction.
• Flat buffer (codes_flat): Row-major storage with one byte per byte-group per vector, enabling block-wise allocation.
• SIMD-blocked (blocked): 32-vector chunks with architecture-specific interleaving for maximum instruction throughput.

Working with Bit-Packed Vectors

Creating an index automatically triggers the full packing pipeline:

use turbovec::{TurboQuantIndex, FromIter};

let dim = 128;  // Must be multiple of 8
let bits = 4;   // 2-bit, 3-bit, or 4-bit quantization
let vectors = vec![/* f32 vectors */];

let idx = TurboQuantIndex::from_iter(vectors.iter().cloned(), dim, bits)
    .expect("valid dimensions and bit width");

For manual control over the packing process:

use turbovec::pack::{repack, repack_seq, seq_to_packed};

let packed_codes: Vec<u8> = /* quantized bit-plane data */;
let n_vectors = 10_000;
let dim = 256;
let bits = 2;

// Convert to SIMD-blocked native layout
let (blocked, n_blocks) = repack(&packed_codes, n_vectors, bits, dim);

// For serialization, use sequential layout
let seq = repack_seq(&packed_codes, n_vectors, bits, dim);

// Round-trip back to bit-plane format
let packed_back = seq_to_packed(&seq, n_vectors, bits, dim);
assert_eq!(packed_back, packed_codes);

Summary

• Quantization reduces each dimension from 32 bits to 2-4 bits, compressing memory by 8-16x.
• Bit-plane storage organizes bits by significance rather than by vector, enabling efficient LUT-based extraction in extract_codes_flat.
• Flat row-major buffers (codes_flat) serve as an intermediate representation that facilitates block-wise reorganization without per-vector allocations.
• 32-vector SIMD blocks align data for high-throughput dot products, with x86-64 using FAISS-style nibble interleaving via pack_blocked while other platforms use sequential layout via pack_blocked_sequential.
• Native transforms allow on-disk sequential data to convert to platform-optimized layouts at load time through apply_native_transform.

Frequently Asked Questions

What bit widths does Turbovec support for compression?

Turbovec supports 2-bit, 3-bit, and 4-bit quantization per dimension. These widths strike a balance between compression ratio and search accuracy, reducing storage from 4 bytes per float to 0.25, 0.375, or 0.5 bytes per dimension respectively.

Why must vector dimensions be a multiple of 8?

The dimension requirement ensures byte-aligned storage for bit-planes. Since the bit-packing scheme stores dim / codes_per_byte bytes per plane, dimensions must divide evenly into byte boundaries to prevent bit-shifting overhead and maintain the alignment requirements of SIMD load instructions.

How does the x86-64 layout differ from the sequential layout?

The x86-64 layout applies FAISS-style nibble interleaving using the PERM0 permutation pattern within pack_blocked, while non-x86 targets use pack_blocked_sequential to store vectors in simple sequential order. Both layouts organize data into 32-vector blocks, but the x86 version rearranges nibbles to optimize for vpdpbusd and sdot SIMD instructions.

Can I convert between packed formats without re-quantizing vectors?

Yes. The seq_to_packed function performs a lossless round-trip conversion between the sequential blocked layout and the original bit-plane format. This allows you to serialize using the portable sequential format and convert to the native SIMD format at runtime without reprocessing the original float vectors.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}