Product Quantization (PQ)

The core mechanism of PQ involves splitting a D-dimensional embedding into M distinct sub-vectors of dimension D/M. Each sub-vector is then independently quantized using a separate codebook of K centroids. This factorization is critical because it avoids the exponential memory cost of quantizing the original vector directly. For a 768-dimensional legal embedding split into 8 sub-vectors with 256 centroids each, the memory footprint drops from 3 KB (float32) to just 8 bytes.

Each sub-vector space is clustered independently using K-Means to generate a codebook. The centroids represent the most common patterns within that subspace of the legal embedding distribution. During encoding, a full vector is compressed by finding the nearest centroid for each sub-vector and storing only the ID of that centroid. The compression ratio is directly controlled by the number of sub-vectors (M) and the codebook size (K), trading recall for memory.

To perform similarity search without decompressing the entire database, PQ uses Asymmetric Distance Computation. The query vector is kept in full precision, while the database vectors remain in compressed form. The distance between the query and a compressed vector is approximated by summing the distances between the query's sub-vectors and the corresponding centroids stored in the database codes. This is efficiently implemented using pre-computed lookup tables, making search extremely fast.

A brute-force scan of billions of compressed codes is still too slow. PQ is typically combined with an Inverted File Index (IVF) to form IVF-PQ. The vector space is first partitioned into Voronoi cells using coarse quantization. A query only probes the nearest cells, and PQ is applied to the residual vectors (the difference between the vector and the coarse centroid). This two-stage approach provides a 10-100x speedup over flat PQ with minimal recall loss for legal document retrieval.

The primary value proposition of PQ is the drastic reduction in RAM requirements for vector indices. A billion 768-dimensional float32 vectors require 3 TB of memory. With PQ (M=96, K=256), this is reduced to approximately 96 GB, fitting comfortably in the memory of a single high-end server. This enables in-memory semantic search over massive legal corpora without relying on slow disk-based retrieval, ensuring sub-100ms latency for multi-document reasoning pipelines.

The fidelity of PQ codebooks is highly dependent on the representativeness of the training data. The K-Means clustering must be performed on a large sample of vectors drawn from the same distribution as the target legal corpus. Using generic embeddings to train codebooks for a specialized legal domain will result in significant quantization error and degraded recall. Best practice involves training codebooks on a representative sample of millions of legal document chunks to capture the unique semantic subspaces of statutory and contractual language.

The class of algorithms that make billion-scale vector search tractable by trading marginal accuracy for massive speed gains. PQ-compressed vectors are indexed using ANN structures to achieve sub-linear search times.

• Core Trade-off: Recall vs. latency vs. memory
• PQ Integration: Compressed vectors reduce distance computation cost within ANN traversal
• Legal Relevance: Enables real-time retrieval over decades of case law without exhaustive scan

A graph-based ANN index that builds a multi-layered navigable structure, achieving logarithmic search complexity. HNSW graphs store PQ-compressed vectors at each node, dramatically reducing the memory required for the index itself.

• Multi-layer design: Top layers enable long-range jumps; bottom layers refine local neighborhoods
• PQ synergy: Quantized vectors fit more nodes in cache, accelerating graph traversal
• Legal use case: Efficiently navigates millions of compressed case embeddings

A training method that produces embeddings where truncated prefixes remain useful for similarity search. Combined with PQ, this enables flexible dimensionality reduction without retraining the encoder.

• Nested structure: First 64 dims capture coarse semantics; full vector captures fine details
• PQ compatibility: Apply quantization to any Matryoshka dimension without re-encoding
• Legal advantage: Store multiple resolution levels of the same document for tiered retrieval

Specialized storage systems designed to index and query high-dimensional embeddings. Modern vector databases natively support PQ compression to reduce the memory footprint of legal document collections by 10-30x.

• Native PQ support: Built-in quantization during index construction
• Disk-backed indices: PQ enables larger-than-memory indexes through efficient disk paging
• Legal scale: Store and search entire regulatory code repositories on commodity hardware

The phenomenon where vector representations degrade in semantic quality as the underlying data distribution shifts. PQ codebooks must be periodically retrained to maintain retrieval accuracy in dynamic legal environments.

• Drift sources: New legislation, evolving judicial interpretation, changing document formats
• Monitoring: Track recall degradation against golden query sets over time
• Remediation: Retrain PQ codebooks on recent document samples without full re-indexing