Quantisation sits at the intersection of information theory and systems engineering, and getting it right matters enormously for large-scale machine learning. When you compress gradients during distributed training, reduce KV-cache footprints for long-context inference, or pack model weights into memory-constrained hardware, the quality of your quantisation scheme directly affects both accuracy and throughput. A paper now on ArXiv, Entropy-Constrained Adaptive Stochastic Quantization, addresses a gap that has been quietly limiting practical quantisation pipelines: existing unbiased adaptive methods choose their codebooks without knowing that a lossless entropy encoder will be applied afterwards.
The gap is not merely academic. Systems like QSGD and distributed mean estimation methods apply entropy coding after quantisation as a matter of course. But the quantisation step itself is solved independently, optimising mean squared error (MSE) for a fixed codebook size without regard to the entropy of the resulting symbol distribution. The result is a suboptimal two-stage pipeline where the entropy encoder cannot compensate for choices made upstream.
The Problem and Why It Is Hard
Adaptive Stochastic Quantization (ASQ) is the current state of the art for unbiased adaptive quantisation. Given an input vector X and a codebook size budget s, ASQ selects quantisation values to minimise expected squared error while preserving the unbiasedness property: each quantised value has the correct expectation. This is solvable optimally in O(d·s) time via dynamic programming, as shown by the QUIVER algorithm.
The ECASQ problem adds an entropy constraint. You now want to minimise MSE subject to both a codebook size limit and a bound on the average-entry entropy of the quantised output. These two constraints interact in a non-trivial way. The entropy of the output depends on how probability mass is distributed across codebook values, which in turn depends on where those values sit relative to the input distribution. The existing ASQ dynamic program cannot be extended to handle this joint optimisation; the authors show this explicitly and construct a new DP from scratch.
The standard approach for entropy-constrained quantisation is to introduce a Lagrange multiplier λ that penalises entropy in the objective, converting the constrained problem into an unconstrained one parameterised by λ. Setting λ = 0 recovers ASQ; large λ forces low entropy at the cost of higher distortion. Sweeping λ traces the convex hull of the Pareto frontier between MSE and entropy. The authors are careful to note that for a given entropy budget b, there may be no single λ that achieves exactly that budget, but a time-sharing scheme between two Lagrangian solutions recovers full optimality across arbitrary budgets.
Key Contributions
- Optimal DP for λ-ECASQ: A dynamic program that solves the Lagrangian relaxation exactly, with complexity reduced from a naive O(p³·s + d) to O(p²·s + d) time and O(p² + d) space using SMAWK acceleration and Hirschberg's divide-and-conquer technique.
- GPU-friendly approximation: An approximate DP with the same asymptotic time complexity but only O(p + d) space, making it practical for large alphabets and amenable to GPU execution. The approximation carries a formal guarantee: its MSE is no worse than the optimal solution using one fewer bit of entropy per entry.
- Iterative refinement: A Lloyd-Max-style refinement procedure applied on top of the approximate solution. Five rounds of refinement close most of the gap to optimal while retaining the speed advantage of the approximate solver.
- Time-sharing for exact entropy targets: A principled mechanism to hit arbitrary entropy budgets by mixing two Lagrangian solutions on a random partition of the input.
Results
Experiments used BF16 synthetic vectors of length 16,384 across four distributions and five random seeds, plus real weight, activation, and KV-cache tensors from Qwen2.5, Gemma-3, Llama-3.2, and Phi-3.5-Mini. The metric is variance-normalised MSE (vNMSE) at matched total rate, where total rate accounts for both the entropy-coded symbols and the codebook representation overhead.
The headline numbers are clear. Unrefined Approx ECASQ sits within 4.97% excess vNMSE of the optimal solution on average, and five rounds of refinement bring this down to 1.37% with a 4.06% maximum across all conditions. Both variants beat every non-ECASQ baseline by a substantial margin: the strongest baseline (entropy-coded QUIVER) shows 23 to 43% excess vNMSE relative to optimal ECASQ. The approximate solver is 24 times faster than the optimal DP at d = 262,144, and the refined version retains a 19x speedup. These gains are consistent across distributions, ranging from 13 to 34x for the unrefined approximation.
Performance on real model tensors follows the same pattern. The method improves over baselines across weight, activation, and KV-cache quantisation tasks for all five model families tested.
Limitations and Open Questions
A few aspects deserve scrutiny. The experiments were conducted on an Apple M2 with 32 GB RAM, which is not a standard ML research or production environment. The GPU-friendliness of the approximate DP is claimed but not benchmarked on actual GPU hardware; the runtime figures are CPU-only. It would be valuable to see how the method performs on A100 or H100 hardware, particularly for the large-vector regimes relevant to LLM inference.
The entropy model used here is the empirical symbol distribution of the quantised vector, which is the natural choice for arithmetic or Huffman coding. However, practical entropy coders often use learned or parametric models; the relationship between the theoretical entropy bound and actual compressed size under such coders is left implicit.
The time-sharing mechanism for hitting exact entropy budgets is theoretically clean but adds implementation complexity. In practice, running two quantisers on a random partition of the input introduces coordination overhead and may interact poorly with systems that process vectors in fixed-size chunks. The authors acknowledge that in practice the single Lagrangian solution is usually sufficient, but this is an empirical observation rather than a guarantee.
The permissible alphabet P is assumed to be given as input, and the paper does not address how to choose it optimally. For BF16 inputs the natural choice is the set of BF16 representable values, but for other formats or mixed-precision settings this choice may matter more than the paper suggests.
More broadly, ECASQ operates in the scalar quantisation regime. Vector quantisation methods can achieve lower distortion at the same rate, and the interaction between entropy-constrained adaptive scalar quantisation and learned vector codebooks (as used in neural compression) is an open direction.
Despite these caveats, the paper makes a genuine contribution. It identifies a real inefficiency in the standard unbiased quantisation pipeline, provides both an exact algorithm and a practical approximation with formal guarantees, and demonstrates consistent empirical gains over competitive baselines. For anyone building compression pipelines for distributed training or LLM inference, this is worth reading carefully. The full paper is available at arxiv.org/abs/2608.18147.