Binary Quantization

Relevant source files

The following files were used as context for generating this wiki page:

• src/quantization/binary.rs
• fuzz/fuzz_targets/quantization/target.rs
• pkg/README.md
• wasm/types.ts
• tests/hybrid_search.rs
• fuzz/FUZZING_STRATEGY.md

Binary Quantization (BQ) is a high-performance vector compression technique implemented in EdgeVec to reduce memory consumption and accelerate similarity searches. It transforms high-dimensional f32 vectors (typically 768 dimensions for standard embeddings) into compact binary representations where each dimension is represented by a single bit. This results in a 32x memory reduction, converting a 3072-byte vector into a 96-byte bitset.

The module facilitates sub-millisecond searches by utilizing Hamming distance instead of Euclidean or Cosine distance. While BQ is an approximate method, EdgeVec achieves ~95% recall when combined with rescoring techniques. BQ is particularly suited for browser-based environments where memory limits and CPU cycles are constrained.

Sources: pkg/README.md:10-15, src/quantization/binary.rs:1-15, wasm/types.ts:168-175

Core Architecture and Algorithm

Binary Quantization operates on a sign-based logic. For every dimension in a source vector, the quantizer evaluates the floating-point value to determine the corresponding bit.

Quantization Logic

The transformation follows a simple rule:

• If vector[i] > 0.0, the $i$-th bit is set to 1.
• If vector[i] <= 0.0, the $i$-th bit is set to 0.

Special floating-point values are handled to ensure stability: NaN results in a 0 bit because the comparison NaN > 0.0 is false per IEEE 754; +Inf results in 1, and -Inf or -0.0 result in 0.

Sources: src/quantization/binary.rs:9-12, src/quantization/binary.rs:43-52

Logic Flow

The following diagram illustrates the data flow from a raw floating-point vector to its compressed binary form.

Data Structures

The system relies on specific Rust structures and TypeScript interfaces to manage the quantized data and its metadata.

QuantizedVector

This is the primary container for compressed data. It is a 96-byte array aligned to 64 bytes to facilitate SIMD (Single Instruction, Multiple Data) optimizations such as AVX-512.

Field	Type	Description
data	[u8; 96]	768 bits of packed sign data.

Sources: src/quantization/binary.rs:66-70, src/quantization/binary.rs:36-40

BinaryQuantizer

A stateless quantizer responsible for the conversion process. It provides methods for fixed-dimension quantization (768D) and flexible quantization for arbitrary lengths.

Sources: src/quantization/binary.rs:163-172

Performance and Complexity

Binary quantization significantly shifts the performance profile of the database by trading a small amount of precision for massive gains in speed and space efficiency.

Resource Impact

Metric	F32 Baseline	Binary Quantization	Improvement
Memory (100k x 768D)	~300 MB	~10 MB	32x Reduction
Search Latency	1x	3x - 5x Faster	High Speedup
Recall@10	100%	~85% (Raw) / ~95% (Rescored)	Minimal Loss

Sources: pkg/README.md:120-130, src/quantization/binary.rs:30-35

Computational Complexity

• Quantization: $O(n)$ time, $O(n/8)$ space.
• Hamming Distance: $O(n/8)$ time using XOR and popcount operations.
• Target: Under 50 CPU cycles per comparison using SIMD.

Sources: src/quantization/binary.rs:25-35, fuzz/fuzz_targets/quantization/target.rs:40-50

Hybrid Search and Rescoring

EdgeVec implements a hybrid search strategy to mitigate the precision loss inherent in binary quantization.

Two-Step Search Process

1. Candidate Generation: The system performs a fast search using BQ and Hamming distance to find $K \times \text{rescoreFactor}$ candidates.
2. Rescoring: The top candidates are rescored using their original f32 representations and the primary distance metric (e.g., L2 or Cosine) to refine the final top $K$ results.

Verification and Invariants

To ensure the "Nvidia Grade" standard, the BQ module is subjected to rigorous fuzz testing to maintain mathematical invariants.

Key Invariants

• Determinism: quantize(v) == quantize(v) for any vector v.
• Self-distance: hamming_distance(q, q) == 0.
• Symmetry: hamming_distance(a, b) == hamming_distance(b, a).
• Boundedness: Distance never exceeds the dimension (768).
• Similarity: Results must stay within the range [0.0, 1.0].

Sources: fuzz/FUZZING_STRATEGY.md:2.1, fuzz/fuzz_targets/quantization/target.rs:37-60

Implementation Snippet

The following Rust implementation demonstrates the bit-packing logic used during quantization:

// From src/quantization/binary.rs:215-225
for (i, &value) in vector.iter().enumerate() {
    if value > 0.0 {
        let byte_idx = i / 8;
        let bit_idx = i % 8;
        data[byte_idx] |= 1 << bit_idx;
    }
}

Sources: src/quantization/binary.rs:215-225

Binary Quantization is a cornerstone of the EdgeVec architecture, enabling large-scale vector operations within the constraints of web browsers and edge environments by prioritizing high compression and rapid bitwise distance calculations.