Entropy-Constrained Adaptive Stochastic Quantization

Researchers introduced Entropy-Constrained Adaptive Stochastic Quantization (ECASQ), a method that jointly selects adaptive quantization values to minimize Mean Squared Error under an entropy budget and unbiasedness constraint, improving compression for machine learning workloads. The approach, detailed in arXiv:2608.18147v1, provides an optimal dynamic program with O(sd^2) time and O(d^2) space, plus a GPU-friendly approximate version with O(sd^2) time and O(d) space, guaranteeing MSE no larger than the optimal solution using one fewer bit of entropy per entry.

arXiv:2608.18147v1 Announce Type: new Abstract: Adaptive stochastic quantization ASQ is a recently introduced quantization approach that optimizes the Mean Squared Error MSE for a given input while preserving unbiasedness. It is designed to alleviate the communication and memory bottlenecks of modern data and machine learning workloads, including model, gradient, and KV-cache compression and nearest-neighbor search. Further, practical systems can then compress quantized data with a lossless entropy encoder. However, existing unbiased methods, including ASQ, choose their quantization values without considering this later encoding stage, leaving accuracy on the table. We formulate the Entropy Constrained Adaptive Stochastic Quantization ECASQ problem, which jointly selects adaptive quantization values to minimize MSE under an entropy budget and an unbiasedness constraint. We give an optimal dynamic program with $O sd^2 $ time and $O d^2 $ space for a length-d vector and at most s quantization values, and a GPU-friendly approximate dynamic program with $O sd^2 $ time and $O d $ space. The approximation guarantees that the solution has an MSE no larger than the optimal solution that uses one fewer bit of entropy per entry. We also provide an iterative refinement procedure for the approximation solution that, in our experiments, yields near-optimal results while retaining a substantial speed advantage over our solver for the optimal solution.