SOPQ: Simple Optimized Product Quantization via Corrected Reverse Water Filling

This paper presents SOPQ. It is a provably correct and one-shot optimization algorithm for optimizing Product Quantization (PQ). The main combinatorial challenge is that of optimally assigning coordinates to *variable-width* PQ segments. OPQ suggests a good fixed-segment-width heuristic. SOPQ, on the other hand, provably approximates the optimal solution. The crux of the algorithm is a novel Corrected Reverse Water Filling (CRWF) formula that accounts for dimension-dependent effects in $k$-means clustering. Thereby, converting the coupled combinatorial problem to standard bin-packing of coordinates to segments by their CRWF allocated bits. We then prove that the SVD rotation globally minimizes the CRWF waterline while simultaneously decorrelating the coordinates. SOPQ outperforms EDEN, E-RaBitQ, TurboQuant, and PQ at low bit rates across five \vqb datasets. It matches OPQ's compression quality while offering strong guarantees, faster and predictable training, and a smaller memory footprint.