Binary Embeddings

Similarity between binary vectors is measured using Hamming distance—the count of differing bits between two vectors. Modern CPUs execute this via the POPCNT (population count) instruction applied to the XOR of two bit strings, making distance calculations orders of magnitude faster than floating-point cosine similarity. For a 768-bit vector, the entire comparison completes in a handful of CPU cycles rather than hundreds of floating-point operations.

A 768-dimensional float32 embedding consumes 3,072 bytes per vector. Its binary equivalent requires only 96 bytes—a 32x reduction. For a corpus of 100 million documents, this shrinks the index from ~286 GB to ~9 GB, allowing entire vector indexes to reside in RAM or even CPU cache, eliminating costly disk I/O during search.

Converting continuous embeddings to binary involves binarization strategies:

• Sign binarization: Map positive values to 1, negative to 0
• Threshold-based: Use the median or learned threshold per dimension
• Learned hashing: Train an end-to-end model with a quantization bottleneck using straight-through estimators
• Iterative quantization (ITQ): Rotate the embedding space to minimize quantization error before binarization

Binary embeddings sacrifice fine-grained similarity for speed. While float32 vectors capture nuanced semantic relationships, binary vectors collapse all magnitude and directional information into a single bit per dimension. This causes ranking degradation—subtle distinctions between highly relevant documents may be lost. The trade-off is acceptable when recall can be recovered through multi-stage retrieval, using binary search for fast candidate generation and a float32 re-ranker for final scoring.

Binary embeddings enable a powerful hybrid architecture: each bit position can be treated as a term in an inverted index. A query vector's set bits map to postings lists, and documents are scored by the number of matching bits. This marries the speed of classic Boolean retrieval with the semantic properties of dense embeddings, allowing systems like Facebook's BGE-M3 or Cohere's Embed v3 to support binary output modes alongside float32.

Binary vector search maps directly to hardware-optimized operations:

• x86 POPCNT: Single-cycle bit counting on modern CPUs
• SIMD instructions: Compare 256 or 512 bits in parallel via AVX2/AVX-512
• FPGA implementations: Custom logic for massively parallel Hamming distance computation
• GPU bitwise kernels: Thousands of concurrent binary comparisons per clock cycle This hardware affinity makes binary embeddings a natural fit for edge deployment and real-time systems with strict latency budgets.

A foundational vector compression technique that decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently using a learned codebook. While binary embeddings use single-bit precision, PQ offers finer granularity by using multi-bit centroids, enabling tunable trade-offs between memory footprint and reconstruction error. Often used as a complementary indexing strategy when binary hash codes alone lack sufficient discriminability.

The primary similarity metric for binary embeddings, defined as the number of bit positions where two vectors differ. Modern CPUs compute this via the POPCNT instruction on XOR results, making it orders of magnitude faster than cosine similarity on dense floats. Key properties:

• Computationally trivial: a single XOR + popcount operation
• Hardware-accelerated on x86 and ARM architectures
• Enables exact nearest neighbor search on millions of vectors in milliseconds

A hashing paradigm where similar inputs map to the same hash bucket with high probability. Binary embeddings can be viewed as a learned form of LSH, where each bit acts as a hyperplane partitioning the space. Classic LSH uses random projections, while modern binary embeddings use neural networks to learn optimal hash functions that preserve semantic similarity, dramatically improving recall over data-independent random hashing.

The class of algorithms that trade a small accuracy loss for massive speed gains in vector search. Binary embeddings accelerate ANN by enabling exact search via bitwise operations on compressed codes, often eliminating the need for approximate graph traversal entirely. Key architectures:

• HNSW: graph-based, logarithmic complexity
• IVF: inverted file with coarse quantization
• Binary hash tables: direct lookup with sub-linear scan

A training methodology producing embeddings that remain useful at multiple truncated dimensions. When combined with binarization, Matryoshka representations allow a single model to output both full-precision dense vectors and compact binary codes at various granularities. This enables adaptive retrieval: use binary codes for fast candidate generation, then re-rank top candidates using the first k dimensions of the full-precision embedding.

The dual-tower neural architecture that encodes queries and documents into independent vector representations. For binary embeddings, the final layer typically applies a sign function or straight-through estimator to binarize the output. Key design choices:

• Symmetric: same encoder for query and document
• Asymmetric: query uses full-precision, document uses binary
• Training loss: contrastive with hard negative mining to preserve semantic boundaries in Hamming space