acceptodds
Withdrawn from ICLR 2027

SOPQ: Simple Optimized Product Quantization via Corrected Reverse Water Filling

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 -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.

Primary area:
optimization
Keywords:
Vector Quantization, SVD, Reverse Water Filling, Product Quantization, KV Compression

Related papers

Discussion (0)

Sign in to comment.