CoChat
Sign Up
Cited by 5Advanced Bandit Algorithms ResearchRecommender Systems and TechniquesDomain Adaptation and Few-Shot Learning

Efficient Prompt Optimization Through the Lens of Best Arm Identification

Open access
Shi, Chengshuai, Yang, Kun, Chen, Zihan, Li, Jundong, Yang, Jing, Shen, Cong·2024·Advances in Neural Information Processing Systems 37
DOI 10.52202/079017-3161
Open this paper in CoChat — free accountOpen PDF

Abstract

The remarkable instruction-following capability of large language models (LLMs) has sparked a growing interest in automatically finding good prompts, i.e., prompt optimization. Most existing works follow the scheme of selecting from a pre-generated pool of candidate prompts. However, these designs mainly focus on the generation strategy, while limited attention has been paid to the selection method. Especially, the cost incurred during the selection (e.g., accessing LLM and evaluating the responses) is rarely explicitly considered. To overcome this limitation, this work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. TRIPLE is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB); thus, it is capable of leveraging the rich toolbox from BAI-FB systematically and also incorporating unique characteristics of prompt optimization. Extensive experiments on multiple well-adopted tasks using various LLMs demonstrate the remarkable performance improvement of TRIPLE over baselines while satisfying the limited budget constraints. As an extension, variants of TRIPLE are proposed to efficiently select examples for few-shot prompts, also achieving superior empirical performance.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.52202/079017-3161

Cites

0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Best-arm identification algorithms are commonly used in model selection and prompt selection, where the goal is to iteratively compare candidates to identify the best option.

    “BAI algorithms are commonly used in model selection (Fu et al., 2024), and been applied to prompt selection (Polo et al., 2024b; Shi et al., 2024), where the goal is to iteratively compare candidates to identify the best option.”

    From Stop Guessing When to Stop Testing: Efficient Model Evaluation with Just Enough Data (2026) · cites this paper as Shi et al., 2024

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 84

  1. Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
  2. Atsidakou, A., Katariya, S., Sanghavi, S., and Kveton, B. (2022). Bayesian fixed-budget best-arm identification. arXiv preprint arXiv:2211.08572. · arXiv
  3. Audibert, J.-Y., Bubeck, S., et al. (2009). Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122.
  4. Audibert, J.-Y., Bubeck, S., and Munos, R. (2010). Best arm identification in multi-armed bandits. In COLT, pages 41-53.
  5. Azizi, M. J., Kveton, B., and Ghavamzadeh, M. (2023). Fixed-budget best-arm identification in structured bandits. arXiv preprint arXiv:2106.04763. · arXiv
  6. Bouneffouf, D. and Rish, I. (2019). A survey on practical applications of multi-armed and contextual bandits. arXiv preprint arXiv:1904.10040. · arXiv
  7. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
  8. Bubeck, S., Cesa-Bianchi, N., et al. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1-122.
  9. Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S., et al. (2023). Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712. · arXiv
  10. Bubeck, S., Wang, T., and Viswanathan, N. (2013). Multiple identifications in multi-armed bandits. In International Conference on Machine Learning, pages 258-265.
  11. PMLR.
  12. Chen, L., Chen, J., Goldstein, T., Huang, H., and Zhou, T. (2023). Instructzero: Ef- ficient instruction optimization for black-box large language models. arXiv preprint arXiv:2306.03082. · arXiv
  13. Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. (2014). Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27.
  14. Chen, W., Hu, W., Li, F., Li, J., Liu, Y., and Lu, P. (2016). Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29.
  15. Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151-159.
  16. PMLR.
  17. Combes, R., Talebi Mazraeh Shahi, M. S., Proutiere, A., et al. (2015). Combinatorial bandits revisited. Advances in neural information processing systems, 28.
  18. Deng, M., Wang, J., Hsieh, C.-P., Wang, Y., Guo, H., Shu, T., Song, M., Xing, E. P., and Hu, Z. (2022). Rlprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv:2205.12548. · arXiv
  19. Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. · arXiv
  20. Diao, S., Huang, Z., Xu, R., Li, X., Lin, Y., Zhou, X., and Zhang, T. (2022). Black-box prompt learning for pre-trained language models. arXiv preprint arXiv:2201.08531. · arXiv
  21. Gabillon, V., Ghavamzadeh, M., and Lazaric, A. (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25.
  22. Gabillon, V., Ghavamzadeh, M., Lazaric, A., and Bubeck, S. (2011). Multi-bandit best arm identification. Advances in Neural Information Processing Systems, 24.
  23. Gai, Y., Krishnamachari, B., and Jain, R. (2012). Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 20(5):1466-1478.
  24. Gao, T., Fisch, A., and Chen, D. (2020). Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012.15723. · arXiv
  25. Garivier, A. and Cappé, O. (2011). The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings.
  26. Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027.
  27. PMLR.
  28. Guo, Q., Wang, R., Guo, J., Li, B., Song, K., Tan, X., Liu, G., Bian, J., and Yang, Y. (2023). Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint arXiv:2309.08532. · arXiv
  29. Hinton, G. E. and Roweis, S. (2002). Stochastic neighbor embedding. In Becker, S., Thrun, S., and Obermayer, K., editors, Advances in Neural Information Processing Systems, volume 15. MIT Press.
  30. Honovich, O., Shaham, U., Bowman, S. R., and Levy, O. (2022). Instruction induction: From few examples to natural language task descriptions. arXiv preprint arXiv:2205.10782. · arXiv
  31. Jamieson, K. and Nowak, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE.
  32. Jedra, Y. and Proutiere, A. (2020). Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 33:10007-10017.
  33. Jiang, Z., Xu, F. F., Araki, J., and Neubig, G. (2020). How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-438.
  34. Kanarios, K., Zhang, Q., and Ying, L. (2024). Cost aware best arm identification. arXiv preprint arXiv:2402.16710. · arXiv
  35. Karnin, Z., Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In International conference on machine learning, pages 1238-1246.
  36. PMLR.
  37. Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22.
  38. Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
  39. Lester, B., Al-Rfou, R., and Constant, N. (2021). The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691. · arXiv
  40. Levy, I., Bogin, B., and Berant, J. (2023). Diverse demonstrations improve in-context compositional generalization. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1401-1422.
  41. Li, X., Lv, K., Yan, H., Lin, T., Zhu, W., Ni, Y., Xie, G., Wang, X., and Qiu, X. (2023). Unified demonstration retriever for in-context learning. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4644-4668.
  42. Li, X. L. and Liang, P. (2021). Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101.00190. · arXiv
  43. Lin, X., Wu, Z., Dai, Z., Hu, W., Shu, Y., Ng, S.-K., Jaillet, P., and Low, B. K. H. (2023). Use your instinct: Instruction optimization using neural bandits coupled with transformers. arXiv preprint arXiv:2310.02905. · arXiv
  44. Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W. (2021a). What makes good in-context examples for gpt-3? arXiv preprint arXiv:2101.06804. · arXiv
  45. Liu, P., Yuan, W., Fu, J., Jiang, Z., Hayashi, H., and Neubig, G. (2023). Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35.
  46. Liu, X., Ji, K., Fu, Y., Tam, W. L., Du, Z., Yang, Z., and Tang, J. (2021b). P-tuning v2: Prompt tuning can be comparable to fine-tuning universally across scales and tasks. arXiv preprint arXiv:2110.07602. · arXiv
  47. Lu, Y., Bartolo, M., Moore, A., Riedel, S., and Stenetorp, P. (2021). Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786. · arXiv
  48. Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2022). Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837. · arXiv
  49. Mishra, S., Khashabi, D., Baral, C., Choi, Y., and Hajishirzi, H. (2021). Reframing instruc- tional prompts to gptk's language. arXiv preprint arXiv:2109.07830. · arXiv
  50. Pan, R., Xing, S., Diao, S., Liu, X., Shum, K., Zhang, J., and Zhang, T. (2023). Plum: Prompt learning using metaheuristic. arXiv preprint arXiv:2311.08364. · arXiv
  51. Prasad, A., Hase, P., Zhou, X., and Bansal, M. (2022). Grips: Gradient-free, edit-based instruction search for prompting large language models. arXiv preprint arXiv:2203.07281. · arXiv
  52. Pryzant, R., Iter, D., Li, J., Lee, Y. T., Zhu, C., and Zeng, M. (2023). Automatic prompt optimization with "gradient descent" and beam search. arXiv preprint arXiv:2305.03495. · arXiv
  53. Rubin, O., Herzig, J., and Berant, J. (2022). Learning to retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2655- 2671.
  54. Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and De Freitas, N. (2015). Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148-175.
  55. Shen, C., Wang, Z., Villar, S., and Van Der Schaar, M. (2020). Learning for dose allocation in adaptive clinical trials with safety constraints. In International Conference on Machine Learning, pages 8730-8740.
  56. PMLR.
  57. Shi, W., Han, X., Gonen, H., Holtzman, A., Tsvetkov, Y., and Zettlemoyer, L. (2022). Toward human readable prompt tuning: Kubrick's the shining is a good movie, and a good prompt too? arXiv preprint arXiv:2212.10539. · arXiv
  58. Shin, T., Razeghi, Y., Logan IV, R. L., Wallace, E., and Singh, S. (2020). Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint arXiv:2010.15980. · arXiv
  59. Soare, M., Lazaric, A., and Munos, R. (2014). Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27.
  60. Su, H., Kasai, J., Wu, C. H., Shi, W., Wang, T., Xin, J., Zhang, R., Ostendorf, M., Zettlemoyer, L., Smith, N. A., et al. (2022). Selective annotation makes language models better few-shot learners. arXiv preprint arXiv:2209.01975. · arXiv
  61. Sun, H., Hüyük, A., and van der Schaar, M. (2023). Query-dependent prompt evaluation and optimization with offline inverse rl. arXiv e-prints, pages arXiv-2309.
  62. Suzgun, M., Scales, N., Schärli, N., Gehrmann, S., Tay, Y., Chung, H. W., Chowdhery, A., Le, Q. V., Chi, E. H., Zhou, D., et al. (2022). Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261. · arXiv
  63. Team, G., Mesnard, T., Hardin, C., Dadashi, R., Bhupatiraju, S., Pathak, S., Sifre, L., Rivière, M., Kale, M. S., Love, J., et al. (2024). Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.08295. · arXiv
  64. Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. (2023a). Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971. · arXiv
  65. Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. (2023b). Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288. · arXiv
  66. Wang, P.-A., Tzeng, R.-C., and Proutiere, A. (2023). Best arm identification with fixed budget: A large deviation perspective. arXiv preprint arXiv:2312.12137. · arXiv
  67. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. (2022). Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837.
  68. Wen, Y., Jain, N., Kirchenbauer, J., Goldblum, M., Geiping, J., and Goldstein, T. (2023). Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. arXiv preprint arXiv:2302.03668. · arXiv
  69. Wu, Z., Wang, S., Gu, J., Hou, R., Dong, Y., Vydiswaran, V., and Ma, H. (2022). Idpg: An instance-dependent prompt generation method. arXiv preprint arXiv:2204.04497. · arXiv
  70. Xu, H., Chen, Y., Du, Y., Shao, N., Wang, Y., Li, H., and Yang, Z. (2022). Gps: Genetic prompt search for efficient few-shot learning. arXiv preprint arXiv:2210.17041. · arXiv
  71. Xu, S. and Zhang, C. (2024). Misconfidence-based demonstration selection for llm in-context learning. arXiv preprint arXiv:2401.06301. · arXiv
  72. Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. (2023). Large language models as optimizers. arXiv preprint arXiv:2309.03409. · arXiv
  73. Yang, J. and Tan, V. (2022). Minimax optimal fixed-budget best arm identification in linear bandits. Advances in Neural Information Processing Systems, 35:12253-12266.
  74. Yavas, R. C. and Tan, V. Y. (2023). Fixed-budget best-arm identification in sparse linear bandits. arXiv preprint arXiv:2311.00481. · arXiv
  75. Zhang, T., Wang, X., Zhou, D., Schuurmans, D., and Gonzalez, J. E. (2023a). Tempera: Test- time prompt editing via reinforcement learning. In The Eleventh International Conference on Learning Representations.
  76. Zhang, Z., Wang, S., Yu, W., Xu, Y., Iter, D., Zeng, Q., Liu, Y., Zhu, C., and Jiang, M. (2023b). Auto-instruct: Automatic instruction generation and ranking for black-box language models. arXiv preprint arXiv:2310.13127. · arXiv
  77. Zhang, Z., Zhang, A., Li, M., and Smola, A. (2022). Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.03493. · arXiv
  78. Zhao, Z., Wallace, E., Feng, S., Klein, D., and Singh, S. (2021). Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning, pages 12697-12706.
  79. PMLR.
  80. Zhong, Z., Friedman, D., and Chen, D. (2021). Factual probing is [mask]: Learning vs. learning to recall. arXiv preprint arXiv:2104.05240. · arXiv
  81. Zhou, D., Li, L., and Gu, Q. (2020). Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502.
  82. PMLR.
  83. Zhou, Y., Muresanu, A. I., Han, Z., Paster, K., Pitis, S., Chan, H., and Ba, J. (2022). Large language models are human-level prompt engineers. arXiv preprint arXiv:2211.01910. · arXiv
  84. Zhu, Y., Zhou, D., Jiang, R., Gu, Q., Willett, R., and Nowak, R. (2021). Pure exploration in kernel and neural bandits. Advances in neural information processing systems, 34:11618- 11630.

Cited by

Sorted by citations

Related

Authors
Shi, C., Yang, K., Chen, Z., Li, J., Yang, J., & Shen, C.
ORCID
Venue
Advances in Neural Information Processing Systems 37
Publisher
Neural Information Processing Systems Foundation, Inc. (NeurIPS)
Published
2024
Pages
99646-99685
ISSN
1049-5258 (ISSN-L)
DOI
10.52202/079017-3161
OpenAlex
W4415796232
Cited by
3
References
0
Citations by year
2026: 2 · 2025: 1
FWCI
2.05
Type
conference paper
Language
en
Open access
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
  • Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
Keywords
prompt optimization, best arm identification, multi-armed bandits, reinforcement learning from human feedback

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review