Search papers, labs, and topics across Lattice.
This paper explores a novel variable bit allocation scheme for quantizing embeddings, challenging the conventional uniform bit allocation approach. By leveraging the geometric structure of embeddings, particularly those with the Matryoshka property, the authors implement a greedy allocation strategy that significantly enhances quantization quality within fixed memory constraints. The findings reveal that non-uniform allocations can improve recall by up to 18% compared to uniform methods, especially in low-bit scenarios, indicating a promising avenue for more efficient compression techniques in large-scale retrieval systems.
Non-uniform bit allocation can boost recall by up to 18% in low-bit quantization, reshaping how we approach embedding compression.
Quantization is a fundamental technique to handle the growing sizes of embeddings generated by modern models. Existing quantization schemes are largely embedding agnostic and allocate bits uniformly across dimensions. However, recent models produce embeddings with significant geometric structure. In this work, we investigate whether a variable bit allocation scheme can improve quantization quality under a fixed memory budget. We propose a simple variable bit allocation framework that partitions an embedding into contiguous buckets and allocates storage non-uniformly across them. Using a greedy allocation strategy, we instantiate this framework for both Product Quantization (PQ) and Scalar Quantization (SQ). We perform a series of experiments on embeddings known to have the Matryoshka property (MRL), and consistently observe that non-uniform allocations outperform uniform baselines at identical storage budgets. The largest improvements occur in the low-bit regime, where uniform allocation is particularly inefficient for MRL embeddings. At the same compression rates, variable allocation improves recall by up to 8\% for PQ and up to 18\% for SQ. Our results suggest a new direction for structure-aware compression and indexing techniques for large-scale retrieval systems.
