Abstract
We study the problem of quantizing $N$ sorted, scalar datapoints with a fixed codebook containing $K$ entries that are allowed to be rescaled. The problem is defined as finding the optimal scaling factor $\alpha$ and the datapoint assignments into the $\alpha$-scaled codebook to minimize the squared error between original and quantized points. Previously, the globally optimal algorithms for this problem were derived only for certain codebooks (binary and ternary) or under the assumption of certain distributions (Gaussian, Laplacian). By studying the properties of the optimal quantizer, we derive an $O(NK \log K)$ algorithm that is guaranteed to find the optimal quantization parameters for any fixed codebook regardless of data distribution. We apply our algorithm to synthetic and real-world neural network quantization problems and demonstrate the effectiveness of our approach.
Introduction
Quantization is a fundamental technique in deep learning, enabling the deployment of large neural networks on resource-constrained hardware by mapping high-precision weights and activations to a smaller set of discrete values, or a "codebook." To maintain accuracy, this codebook is typically rescaled by a factor $\alpha$.
Finding the optimal $\alpha$ is a non-trivial optimization problem. A large $\alpha$ increases the resolution for large values but sacrifices precision for smaller ones, while a small $\alpha$ leads to "clipping" of outliers. Existing frameworks often rely on heuristics, such as the "min-max" approach or specific percentiles, or iterative methods like alternating optimization ("alt-opt"). However, these methods frequently fail to find the global minimum, especially in low-precision settings (e.g., 4-bit quantization) where the error surface has many local minima.
Characterizing the Optimum
The core challenge in finding the global optimum is that the objective function—Mean Squared Error (MSE)—is non-convex with respect to $\alpha$. The researchers' key insight was to characterize the structure of the optimal solution. They proved that for sorted data, the optimal assignment of data points to codebook entries always forms continuous "chunks."
Furthermore, they discovered that the entire range of possible $\alpha$ values can be partitioned into at most $NK + 1$ regions. Within each region, the optimal assignment of points to the codebook remains constant. This observation transforms a continuous, non-convex search into a discrete optimization problem over a finite number of regions.
The Optimal Algorithm
Building on this characterization, the authors developed an efficient algorithm to find the global optimum. While a naive search through all regions would take $O(NK^2 \log N)$ time, the optimized version (Algorithm 3) utilizes a min-heap data structure and cumulative sums. This allows the algorithm to update the error and scaling factor in constant time as it traverses the regions, resulting in a total complexity of $O(NK \log K)$. This efficiency makes the algorithm a practical drop-in replacement for existing calibration steps in post-training quantization pipelines.
Experimental Results
The proposed method was evaluated against standard heuristics and iterative solvers using both synthetic and real-world datasets.
Synthetic Data
To test the "distribution-agnostic" nature of the algorithm, the authors used a mixture of three Gaussians. This multi-modal distribution is challenging for methods that assume Gaussian or Laplacian priors.
As shown in the results, the proposed "OPT" algorithm consistently achieves lower MSE than both the min-max heuristic and the alternating optimization approach. The gap is particularly pronounced at lower bit-widths (2-4 bits), where the choice of scale is most critical.
Neural Network Benchmarks
The algorithm's impact is most visible in post-training quantization (PTQ) for image classification. On the ImageNet2012 benchmark, the optimal MSE quantization significantly outperformed standard methods. For example, when quantizing ResNet50 to INT4:
- Min-Max Heuristic: 0.21% Top-1 Accuracy
- Proposed OPT Algorithm: 63.74% Top-1 Accuracy
This dramatic improvement demonstrates that finding the global optimum for $\alpha$ is critical for maintaining the performance of low-precision neural networks.
Conclusion
This work provides the first efficient algorithm guaranteed to find the globally optimal scaling factor for any fixed codebook and any data distribution. By reducing the complexity to $O(NK \log K)$, the authors have turned a theoretically difficult problem into a practical tool for the deep learning community. Future work may extend this approach to vector quantization or the co-optimization of codebook entries and scaling factors, potentially adapting for novel hardware-specific number formats.
Summary updated