{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T03:10:45Z","timestamp":1782184245391,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>Large Language Models (LLMs) have recently demonstrated exceptional performance in various real-world data management tasks through in-context learning (ICL), which involves structuring prompts with task descriptions and several demonstrations. However, most LLMs are not free and charge based on the number of input tokens. Specifically, for data management tasks, there may be massive related questions, leading to high inference cost due to redundant prompt content (i.e., overlapping demonstrations and repeated task descriptions). In this paper, we investigate the idea of batch prompting in leveraging LLMs for data management, which leads to cost-effective LLMs by grouping questions and demonstrations to perform inferences in batches. Current studies on batch prompting are preliminary and mostly based on heuristics, making it difficult to generalize to various types of tasks and adapt to different grouping strategies. To address these challenges, in this work we first formalize the batch prompting problem in general setting. Then, we study the hardness of this problem and propose efficient algorithms for adaptive grouping. Finally, we conduct comprehensive experiments on 14 datasets. Extensive experimental results demonstrate that our solution consistently outperforms the state-of-the-art baselines while consuming lower cost.<\/jats:p>","DOI":"10.14778\/3734839.3734853","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:06Z","timestamp":1756483266000},"page":"2172-2184","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimized Batch Prompting for Cost-Effective LLMs"],"prefix":"10.14778","volume":"18","author":[{"given":"Zhaoxuan","family":"Ji","sequence":"first","affiliation":[{"name":"School of Computer Science &amp; Technology, Beijing Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xinlu","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science &amp; Technology, Beijing Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhaojing","family":"Luo","sequence":"additional","affiliation":[{"name":"School of Computer Science &amp; Technology, Beijing Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhongle","family":"Xie","sequence":"additional","affiliation":[{"name":"The State Key Laboratory of Blockchain and Data Security, Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meihui","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science &amp; Technology, Beijing Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2025. Gurobi Optimizer Reference Manual. https:\/\/www.pgurobi.com."},{"key":"e_1_2_1_2_1","unstructured":"2025. OpenAI API. https:\/\/platform.openai.com\/."},{"key":"e_1_2_1_3_1","unstructured":"2025. Technical Report. https:\/\/github.com\/jzx-bitdb\/BatchPrompt\/blob\/main\/technical_report.pdf."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498319"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3626292.3626294"},{"key":"e_1_2_1_7_1","volume-title":"Correlation clustering. Machine learning 56","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine learning 56 (2004), 89\u2013113."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591300"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904489"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2023.emnlp-industry.74"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.05.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639279"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies","volume":"1","author":"Devlin Jacob","year":"2019","unstructured":"Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). 4171\u20134186."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3405476"},{"key":"e_1_2_1_16_1","volume-title":"A survey on in-context learning. arXiv preprint arXiv:2301.00234","author":"Dong Qingxiu","year":"2022","unstructured":"Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui. 2022. A survey on in-context learning. arXiv preprint arXiv:2301.00234 (2022)."},{"key":"e_1_2_1_17_1","volume-title":"30th International symposium on theoretical aspects of computer science (STACS","author":"D\u00f3sa Gy\u00f6rgy","year":"2013","unstructured":"Gy\u00f6rgy D\u00f3sa and Jir\u00ed Sgall. 2013. First Fit bin packing: A tight analysis. In 30th International symposium on theoretical aspects of computer science (STACS 2013). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00284"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611527"},{"key":"e_1_2_1_20_1","volume-title":"ArcheType: A Novel Framework for Open-Source Column Type Annotation using Large Language Models. arXiv preprint arXiv:2310.18208","author":"Feuer Benjamin","year":"2023","unstructured":"Benjamin Feuer, Yurong Liu, Chinmay Hegde, and Juliana Freire. 2023. ArcheType: A Novel Framework for Open-Source Column Type Annotation using Large Language Models. arXiv preprint arXiv:2310.18208 (2023)."},{"key":"e_1_2_1_21_1","first-page":"1034","article-title":"Text-to-SQL Empowered by Large Language Models: A Benchmark Evaluation","volume":"17","author":"Gao Dawei","year":"2023","unstructured":"Dawei Gao, Haibin Wang, Yaliang Li, Xiuyu Sun, Yichen Qian, Bolin Ding, and Jingren Zhou. 2023. Text-to-SQL Empowered by Large Language Models: A Benchmark Evaluation. Proceedings of the VLDB Endowment 17, 10 (2023), 1034\u20131045.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Michael R Garey and David S Johnson. 1981. Approximation algorithms for bin packing problems: A survey. In Analysis and design of algorithms in combinatorial optimization. 147\u2013172.","DOI":"10.1007\/978-3-7091-2748-3_8"},{"key":"e_1_2_1_23_1","volume-title":"LongIns: A Challenging Long-context Instruction-based Exam for LLMs. arXiv preprint arXiv:2406.17588","author":"Gavin Shawn","year":"2024","unstructured":"Shawn Gavin, Tuney Zheng, Jiaheng Liu, Quehry Que, Noah Wang, Jian Yang, Chenchen Zhang, Wenhao Huang, Wenhu Chen, and Ge Zhang. 2024. LongIns: A Challenging Long-context Instruction-based Exam for LLMs. arXiv preprint arXiv:2406.17588 (2024)."},{"key":"e_1_2_1_24_1","volume-title":"LLM Maybe LongLM: SelfExtend LLM Context Window Without Tuning. In Forty-first International Conference on Machine Learning.","author":"Jin Hongye","year":"2024","unstructured":"Hongye Jin, Xiaotian Han, Jingfeng Yang, Zhimeng Jiang, Zirui Liu, Chia-Yuan Chang, Huiyuan Chen, and Xia Hu. 2024. LLM Maybe LongLM: SelfExtend LLM Context Window Without Tuning. In Forty-first International Conference on Machine Learning."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407831"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659461"},{"key":"e_1_2_1_27_1","volume-title":"BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystack. arXiv preprint arXiv:2406.10149","author":"Kuratov Yuri","year":"2024","unstructured":"Yuri Kuratov, Aydar Bulatov, Petr Anokhin, Ivan Rodkin, Dmitry Sorokin, Artyom Sorokin, and Mikhail Burtsev. 2024. BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystack. arXiv preprint arXiv:2406.10149 (2024)."},{"key":"e_1_2_1_28_1","volume-title":"Xiang Yue, and Wenhu Chen.","author":"Li Tianle","year":"2024","unstructured":"Tianle Li, Ge Zhang, Quy Duc Do, Xiang Yue, and Wenhu Chen. 2024. Long-context LLMs Struggle with Long In-context Learning. CoRR (2024)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421431"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00051"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588936"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00146"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574258"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192973"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00205"},{"key":"e_1_2_1_36_1","volume-title":"Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. arXiv preprint arXiv:1908.10084","author":"Reimers N","year":"2019","unstructured":"N Reimers. 2019. Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. arXiv preprint arXiv:1908.10084 (2019)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517870"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380429"},{"key":"e_1_2_1_39_1","volume-title":"Denny Zhou, et al.","author":"Wei Jason","year":"2022","unstructured":"Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35 (2022), 24824\u201324837."},{"key":"e_1_2_1_40_1","volume-title":"Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. Advances in Neural Information Processing Systems 36","author":"Wen Yuxin","year":"2024","unstructured":"Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein. 2024. Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. Advances in Neural Information Processing Systems 36 (2024)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2022.acl-long.174"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3069861"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00441"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659452"},{"key":"e_1_2_1_45_1","unstructured":"Wayne Xin Zhao Kun Zhou Junyi Li Tianyi Tang Xiaolei Wang Yupeng Hou Yingqian Min Beichen Zhang Junjie Zhang Zican Dong et al. 2023. A survey of large language models. arXiv preprint arXiv:2303.18223 (2023)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115409"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3664647.3681190"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636233"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3734839.3734853","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:32Z","timestamp":1756483292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3734839.3734853"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":48,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.14778\/3734839.3734853"],"URL":"https:\/\/doi.org\/10.14778\/3734839.3734853","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}