{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:45:58Z","timestamp":1787017558274,"version":"build-2736575974"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T00:00:00Z","timestamp":1764633600000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2101140, CNS-2107078, DMS-2023528"],"award-info":[{"award-number":["CCF-2101140, CNS-2107078, DMS-2023528"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>\n                    Quantization is used to convert higher-precision data into a lower-precision representation, providing a fundamental technique to reduce memory usage, computational complexity, and communication costs in machine learning tasks. Recently, Adaptive Stochastic Quantization (ASQ) methods, which provide unbiased optimized quantized values for\n                    <jats:italic toggle=\"yes\">a specific input<\/jats:italic>\n                    (i.e., when the input distribution is not known to the dequantizer), have been shown to be efficient for compressing large tensors on the fly.\n                  <\/jats:p>\n                  <jats:p>In this paper, we introduce the Adaptive Unbiased Quantization (AUQ) problem that generalizes ASQ to a setting where shared randomness known to both the quantizer and the dequantizer is allowed. We prove an asymptotic gap between the achievable accuracy of the problems, showing that AUQ can be quadratically more precise. We then introduce Simba, an AUQ technique that improves the accuracy of optimal ASQ methods. Intuitively, Simba uses multiple sets of quantization values, and the set used to quantize a specific value is determined using the shared randomness. Interestingly, we show that Simba improves both the speed and accuracy of optimal ASQ methods by leveraging an approximate ASQ solution as a starting point from which Simba improves. We measure Simba to be up to \u2248 24\u00d7 more accurate for popular distributions than the state-of-the-art optimal ASQ method, QUIVER, while also being up to two orders of magnitude faster. Finally, we demonstrate that Simba can be used to improve the accuracy of QUIC-FL, a state-of-the-art Distributed Mean Estimation technique, by replacing its solver-based lookup tables with tables computed by Simba.<\/jats:p>","DOI":"10.1145\/3771564","type":"journal-article","created":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T20:07:03Z","timestamp":1764706023000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Better than Optimal: Improving Adaptive Stochastic Quantization Using Shared Randomness"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0196-9190","authenticated-orcid":false,"given":"Ran","family":"Ben Basat","sequence":"first","affiliation":[{"name":"University College London, London, United Kingdom and Broadcom, Palo Alto, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3844-5940","authenticated-orcid":false,"given":"Yaniv","family":"Ben-Itzhak","sequence":"additional","affiliation":[{"name":"Broadcom, Palo Alto, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5430-5457","authenticated-orcid":false,"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0982-7894","authenticated-orcid":false,"given":"Shay","family":"Vargaftik","sequence":"additional","affiliation":[{"name":"Broadcom, Palo Alto, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,2]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"3329","volume-title":"PMLR","author":"Suresh A. T.","year":"2017","unstructured":"A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan, ''Distributed Mean Estimation With Limited Communication,'' in International Conference on Machine Learning. PMLR, 2017, pp. 3329-3337."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3389\/fams.2018.00062"},{"key":"e_1_2_1_3_1","volume-title":"Expanding the Reach of Federated Learning by Reducing Client Resource Requirements,'' arXiv preprint arXiv:1812.07210","author":"Caldas S.","year":"2018","unstructured":"S. Caldas, J. Kone\u010dn\u1ef3, H. B. McMahan, and A. Talwalkar, ''Expanding the Reach of Federated Learning by Reducing Client Resource Requirements,'' arXiv preprint arXiv:1812.07210, 2018."},{"key":"e_1_2_1_4_1","first-page":"21","volume-title":"PMLR","author":"Vargaftik S.","year":"2022","unstructured":"S. Vargaftik, R. B. Basat, A. Portnoy, G. Mendelson, Y. B. Itzhak, and M. Mitzenmacher, ''EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning,'' in International Conference on Machine Learning. PMLR, 2022, pp. 21,984-22,014."},{"key":"e_1_2_1_5_1","first-page":"8356","volume-title":"PMLR","author":"Dorfman R.","year":"2023","unstructured":"R. Dorfman, S. Vargaftik, Y. Ben-Itzhak, and K. Y. Levy, ''DoCoFL: downlink compression for cross-device federated learning,'' in International Conference on Machine Learning. PMLR, 2023, pp. 8356-8388."},{"key":"e_1_2_1_6_1","volume-title":"Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression,'' in HotNets","author":"Han W.","year":"2024","unstructured":"W. Han, S. Vargaftik, M. Mitzenmacher, B. Karp, and R. Ben Basat, ''Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression,'' in HotNets, 2024."},{"key":"e_1_2_1_7_1","volume-title":"OPTQ: Accurate quantization for generative pre-trained transformers,'' in The Eleventh International Conference on Learning Representations","author":"Frantar E.","year":"2023","unstructured":"E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, ''OPTQ: Accurate quantization for generative pre-trained transformers,'' in The Eleventh International Conference on Learning Representations, 2023."},{"key":"e_1_2_1_8_1","first-page":"14","volume-title":"Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing","author":"Jeon Y.","year":"2023","unstructured":"Y. Jeon, C. Lee, K. Park, and H.-y. Kim, ''A Frustratingly Easy Post-Training Quantization Scheme for LLMs,'' in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 14,446-14,461."},{"key":"e_1_2_1_9_1","volume-title":"Towards next-level post-training quantization of hyper-scale transformers,'' in NeurIPS","author":"Kim J.","year":"2024","unstructured":"J. Kim, S. Lee, and M. Park, ''Towards next-level post-training quantization of hyper-scale transformers,'' in NeurIPS, 2024."},{"key":"e_1_2_1_10_1","volume-title":"Boa: Attention-aware post-training quantization without backpropagation,'' in ICML","author":"Kim J.","year":"2025","unstructured":"J. Kim, A. Gupta, and Y. Tan, ''Boa: Attention-aware post-training quantization without backpropagation,'' in ICML, 2025."},{"key":"e_1_2_1_11_1","volume-title":"Venkatesh et al., ''Mixed Precision Training,'' in International Conference on Learning Representations","author":"Micikevicius P.","year":"2018","unstructured":"P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh et al., ''Mixed Precision Training,'' in International Conference on Learning Representations, 2018."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i05.6409"},{"key":"e_1_2_1_13_1","volume-title":"Reshape and adapt for output quantization (raoq): Quantization-aware training for in-memory computing systems,'' in ICML","author":"Doe J.","year":"2024","unstructured":"J. Doe and L. Smith, ''Reshape and adapt for output quantization (raoq): Quantization-aware training for in-memory computing systems,'' in ICML, 2024."},{"key":"e_1_2_1_14_1","first-page":"31","volume-title":"PMLR","author":"Sheng Y.","year":"2023","unstructured":"Y. Sheng, L. Zheng, B. Yuan, Z. Li, M. Ryabinin, B. Chen, P. Liang, C. R\u00e9, I. Stoica, and C. Zhang, ''Flexgen: High-Throughput Generative Inference of Large Language Models With a Single GPU,'' in International Conference on Machine Learning. PMLR, 2023, pp. 31,094-31,116."},{"key":"e_1_2_1_15_1","volume-title":"Minicache: Kv cache compression in depth dimension for large language models,'' in NeurIPS","author":"Liu Y.","year":"2024","unstructured":"Y. Liu, D. Kim, and J. Park, ''Minicache: Kv cache compression in depth dimension for large language models,'' in NeurIPS, 2024."},{"key":"e_1_2_1_16_1","volume-title":"Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization,'' in NeurIPS","author":"Zhang X.","year":"2024","unstructured":"X. Zhang, Y. Li, and Q. Zhou, ''Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization,'' in NeurIPS, 2024."},{"key":"e_1_2_1_17_1","volume-title":"Hack: Homomorphic acceleration via compression of the key-value cache for disaggregated llm inference,'' arXiv preprint arXiv:2502.03589","author":"Zhang Z.","year":"2025","unstructured":"Z. Zhang, H. Shen, S. Vargaftik, R. B. Basat, M. Mitzenmacher, and M. Yu, ''Hack: Homomorphic acceleration via compression of the key-value cache for disaggregated llm inference,'' arXiv preprint arXiv:2502.03589, 2025."},{"key":"e_1_2_1_18_1","first-page":"17","article-title":"Dataset Quantization","author":"Zhou D.","year":"2023","unstructured":"D. Zhou, K. Wang, J. Gu, X. Peng, D. Lian, Y. Zhang, Y. You, and J. Feng, ''Dataset Quantization,'' in Proceedings of the IEEE\/CVF International Conference on Computer Vision, 2023, pp. 17,205-17,216.","journal-title":"Proceedings of the IEEE\/CVF International Conference on Computer Vision"},{"key":"e_1_2_1_19_1","volume-title":"Atom: Attention mixer for efficient dataset distillation,'' in CVPR","author":"Khaki S.","year":"2024","unstructured":"S. Khaki, A. Sajedi, K. Wang, L. Z. Liu, Y. A. Lawryshyn, and K. N. Plataniotis, ''Atom: Attention mixer for efficient dataset distillation,'' in CVPR, 2024."},{"key":"e_1_2_1_20_1","first-page":"1709","article-title":"QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding","volume":"30","author":"Alistarh D.","year":"2017","unstructured":"D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, ''QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding,'' Advances in Neural Information Processing Systems, vol. 30, pp. 1709-1720, 2017.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_21_1","volume-title":"Accelerating Federated Learning with Quick Distributed Mean Estimation,'' in International Conference on Machine Learning","author":"Basat R. B.","year":"2024","unstructured":"R. B. Basat, S. Vargaftik, A. Portnoy, G. Einziger, Y. Ben-Itzhak, and M. Mitzenmacher, ''Accelerating Federated Learning with Quick Distributed Mean Estimation,'' in International Conference on Machine Learning, 2024."},{"key":"e_1_2_1_22_1","first-page":"4035","volume-title":"PMLR","author":"Zhang H.","year":"2017","unstructured":"H. Zhang, J. Li, K. Kara, D. Alistarh, J. Liu, and C. Zhang, ''ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning,'' in International Conference on Machine Learning. PMLR, 2017, pp. 4035-4043."},{"key":"e_1_2_1_23_1","first-page":"3174","volume-title":"Adaptive Gradient Quantization for Data-parallel SGD,'' Advances in neural information processing systems","author":"Faghri F.","year":"2020","unstructured":"F. Faghri, I. Tabrizian, I. Markov, D. Alistarh, D. M. Roy, and A. Ramezani-Kebrya, ''Adaptive Gradient Quantization for Data-parallel SGD,'' Advances in neural information processing systems, vol. 33, pp. 3174-3185, 2020."},{"key":"e_1_2_1_24_1","first-page":"94","article-title":"Optimal and approximate adaptive stochastic quantization","volume":"37","author":"Ben-Basat R.","year":"2024","unstructured":"R. Ben-Basat, Y. Ben-Itzhak, M. Mitzenmacher, and S. Vargaftik, ''Optimal and approximate adaptive stochastic quantization,'' Advances in Neural Information Processing Systems, vol. 37, pp. 94,265-94,291, 2024.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_25_1","first-page":"362","article-title":"Drive: One-bit Distributed Mean Estimation","volume":"34","author":"Vargaftik S.","year":"2021","unstructured":"S. Vargaftik, R. Ben-Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzenmacher, ''Drive: One-bit Distributed Mean Estimation,'' Advances in Neural Information Processing Systems, vol. 34, pp. 362-377, 2021.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_26_1","first-page":"7197","volume-title":"PMLR","author":"Nagel M.","year":"2020","unstructured":"M. Nagel, R. A. Amjad, M. Van Baalen, C. Louizos, and T. Blankevoort, ''Up or Down? Adaptive Rounding for Post-training Quantization,'' in International Conference on Machine Learning. PMLR, 2020, pp. 7197-7206."},{"key":"e_1_2_1_27_1","first-page":"1737","volume-title":"PMLR","author":"Gupta S.","year":"2015","unstructured":"S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan, ''Deep learning with limited numerical precision,'' in International conference on machine learning. PMLR, 2015, pp. 1737-1746."},{"issue":"1","key":"e_1_2_1_28_1","first-page":"5074","article-title":"NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization","volume":"22","author":"Ramezani-Kebrya A.","year":"2021","unstructured":"A. Ramezani-Kebrya, F. Faghri, I. Markov, V. Aksenov, D. Alistarh, and D. M. Roy, ''NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization,'' The Journal of Machine Learning Research, vol. 22, no. 1, pp. 5074-5116, 2021.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_2_1_29_1","first-page":"25","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021","volume":"198","author":"Basat Ben","year":"2021","unstructured":"Ben Basat, Ran and Mitzenmacher, Michael and Vargaftik, Shay, ''How to Send a Real Number Using a Single Bit (And Some Shared Randomness),'' in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), vol. 198, 2021, p. 25."},{"key":"e_1_2_1_30_1","article-title":"Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor","author":"Safaryan M.","year":"2020","unstructured":"M. Safaryan, E. Shulgin, and P. Richt\u00e1rik, ''Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor,'' Information and Inference: A Journal of the IMA, 2020.","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"e_1_2_1_31_1","volume-title":"When ML Training Cuts Through Congestion: Just-in-Time Gradient Compression via Packet Trimming,'' in Hotnets","author":"Chen X.","year":"2024","unstructured":"X. Chen, S. Vargaftik, and R. Ben-Basat, ''When ML Training Cuts Through Congestion: Just-in-Time Gradient Compression via Packet Trimming,'' in Hotnets, 2024."},{"key":"e_1_2_1_32_1","volume-title":"THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression,'' in USENIX Symposium on Networked Systems Design and Implementation","author":"Li M.","year":"2024","unstructured":"M. Li, R. B. Basat, S. Vargaftik, C. Lao, K. Xu, X. Tang, M. Mitzenmacher, and M. Yu, ''THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression,'' in USENIX Symposium on Networked Systems Design and Implementation, 2024."},{"key":"e_1_2_1_33_1","unstructured":"''Simba code '' https:\/\/github.com\/ranbenbasat\/Simba."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_35_1","unstructured":"''QUIVER code '' https:\/\/github.com\/ranbenbasat\/QUIVER."},{"key":"e_1_2_1_36_1","first-page":"676","volume-title":"Efficient Sparse Collective Communication and its Application to Accelerate Distributed Deep Learning,'' in Proceedings of the 2021 ACM SIGCOMM 2021 Conference","author":"Fei J.","year":"2021","unstructured":"J. Fei, C.-Y. Ho, A. N. Sahu, M. Canini, and A. Sapio, ''Efficient Sparse Collective Communication and its Application to Accelerate Distributed Deep Learning,'' in Proceedings of the 2021 ACM SIGCOMM 2021 Conference, 2021, pp. 676-691."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3696348.3696857"},{"key":"e_1_2_1_38_1","volume-title":"PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization,'' in Advances in Neural Information Processing Systems","author":"Vogels T.","year":"2019","unstructured":"T. Vogels, S. P. Karimireddy, and M. Jaggi, ''PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization,'' in Advances in Neural Information Processing Systems, vol. 32, 2019."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2020.3016905"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3696348.3696880"},{"key":"e_1_2_1_41_1","first-page":"1251","volume-title":"IEEE","author":"Basat R. B.","year":"2020","unstructured":"R. B. Basat, G. Einziger, M. Mitzenmacher, and S. Vargaftik, ''Faster and more accurate measurement through additive-error counters,'' in IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 1251-1260."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386367.3431303"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771564","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771564","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:26:29Z","timestamp":1764782789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3771564"],"URL":"https:\/\/doi.org\/10.1145\/3771564","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-12-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}