Elamur Research
☰
home / papers / 2023 / Automatic Prompt Optimization with ``Gradient Descent'' and Beam Search

Automatic Prompt Optimization with ``Gradient Descent'' and Beam Search

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/2023.emnlp-main.494.pdf

Summary

Writing prompts for LLMs is still mostly manual trial and error. Many existing automatic methods need access to model internals, or they search the prompt space without a clear direction. The authors introduce ProTeGi (Prompt Optimization with Textual Gradients), a nonparametric method that needs only labelled training examples and a black-box LLM API. It imitates gradient descent in text. The LLM examines a prompt's errors on a minibatch and writes a critique, which serves as the textual "gradient". A second prompt then rewrites the original to fix the problems the critique describes, and paraphrasing adds more candidates. These candidates feed a beam search. Deciding which candidates survive is treated as a best arm identification problem and solved with bandit algorithms to limit evaluation cost. Across three benchmark NLP classification tasks and a new LLM jailbreak detection task, ProTeGi improved starting prompts by up to 31%. It also beat earlier prompt-editing baselines by 4–8% on average while using fewer API calls. This matters because it turns vague task descriptions into precise, readable instructions without model training or hyperparameter tuning.

Key points

  • Core loop: a feedback prompt (∇) summarizes the current prompt's flaws from its minibatch errors. An editing prompt (δ) produces improved versions, and a paraphrasing step (LLM_mc) explores nearby wordings.
  • Candidate selection: the paper considers UCB, UCB-E and Successive Rejects bandits. Successive Rejects is provably optimal for best arm identification and needs no hyperparameters.
  • Evaluation: four classification tasks, including Ethos (hate speech) and the newly proposed jailbreak detection problem. Baselines include Monte Carlo (MC) paraphrase search and an RL-based prompt editor.
  • Results: up to 31% gain over the initial prompt and an average 4–8% gain over state-of-the-art prompt learning baselines, with fewer LLM API calls.
  • Limitations and resources:
    • API rate limits and the many calls required can push runtime past an hour.
    • Testing was limited to classification tasks.
    • Code and data are available at github.com/microsoft/LMOps (prompt_optimization).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

210 papers of our library cite it (of the 140673 whose bibliographies we read); 6 of them have a page here, 204 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2023.emnlp-main.494

@inproceedings{pryzant2023automatic,
  title = {{Automatic Prompt Optimization with ``Gradient Descent'' and Beam Search}},
  author = {Pryzant, Reid and Iter, Dan and Li, Jerry and Lee, Yin and Zhu, Chenguang and Zeng, Michael},
  booktitle = {Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing},
  year = {2023},
  doi = {10.18653/v1/2023.emnlp-main.494},
  url = {https://doi.org/10.18653/v1/2023.emnlp-main.494}
}

References

31 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. 2010. Best arm identification in multi-armed bandits. In COLT, pages 41–53. find
  2. Steven Bird. 2006. Nltk: the natural language toolkit. In Proceedings of the COLING/ACL 2006 Interactive Presentation Sessions, pages 69–72. find
  3. Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. 2012. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1–122. find
  4. Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. 2023. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712. find our card
  5. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128. find
  6. Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu. 2022. Rlprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv:2205.12548. find our card
  7. Ibrahim Abu Farha and Walid Magdy. 2020. From arabic sentiment analysis to sarcasm detection: The arsarcasm dataset. In Proceedings of the 4th Workshop on Open-Source Arabic Corpora and Processing Tools, with a Shared Task on Offensive Language Detection, pages 32–39. find our card
  8. Tianyu Gao, Adam Fisch, and Danqi Chen. 2020. Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012.15723. find our card
  9. Yiduo Guo, Yaobo Liang, Chenfei Wu, Wenshan Wu, Dongyan Zhao, and Nan Duan. 2023. Learning to program with natural language. arXiv preprint arXiv:2304.10464. — [arXiv:2304.10464](https://arxiv.org/abs/2304.10464) find
  10. Karen Hambardzumyan, Hrant Khachatrian, and Jonathan May. 2021. Warp: Word-level adversarial reprogramming. arXiv preprint arXiv:2101.00121. find
  11. Yaru Hao, Zewen Chi, Li Dong, and Furu Wei. 2022. Optimizing prompts for text-to-image generation. arXiv preprint arXiv:2212.09611. — [arXiv:2212.09611](https://arxiv.org/abs/2212.09611) find
  12. Or Honovich, Uri Shaham, Samuel R Bowman, and Omer Levy. 2022. Instruction induction: From few examples to natural language task descriptions. arXiv preprint arXiv:2205.10782. find
  13. Ellen Jiang, Kristen Olson, Edwin Toh, Alejandra Molina, Aaron Donsbach, Michael Terry, and Carrie J Cai. 2022. Promptmaker: Prompt-based prototyping with large language models. In CHI Conference on Human Factors in Computing Systems Extended Abstracts, pages 1–8. find
  14. Zohar Karnin, Tomer Koren, and Oren Somekh. 2013. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238–1246. PMLR. find
  15. Volodymyr Kuleshov and Doina Precup. 2014. Algorithms for multi-armed bandit problems. arXiv preprint arXiv:1402.6028. — [arXiv:1402.6028](https://arxiv.org/abs/1402.6028) find
  16. Brian Lester, Rami Al-Rfou, and Noah Constant. 2021. The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691. find
  17. Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022. Competition-level code generation with alphacode. Science, 378(6624):1092–1097. find our card
  18. Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2021. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786. find our card
  19. Ioannis Mollas, Zoe Chrysopoulou, Stamatis Karlos, and Grigorios Tsoumakas. 2020. Ethos: an online hate speech detection dataset. arXiv preprint arXiv:2006.08328. — [arXiv:2006.08328](https://arxiv.org/abs/2006.08328) find
  20. OpenAI. 2023. Gpt-4 technical report. find our card
  21. Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2022. Grips: Gradient-free, edit-based instruction search for prompting large language models. arXiv preprint arXiv:2203.07281. find
  22. Guanghui Qin and Jason Eisner. 2021. Learning how to ask: Querying lms with mixtures of soft prompts. arXiv preprint arXiv:2104.06599. find our card
  23. Laria Reynolds and Kyle McDonell. 2021. Prompt programming for large language models: Beyond the few-shot paradigm. In Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems, pages 1–7. find our card
  24. Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. 2020. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint arXiv:2010.15980. find our card
  25. William Yang Wang. 2017. " liar, liar pants on fire": A new benchmark dataset for fake news detection. arXiv preprint arXiv:1705.00648. find our card
  26. Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannaneh Hajishirzi. 2022. Self-instruct: Aligning language model with self generated instructions. arXiv preprint arXiv:2212.10560. find
  27. Hanwei Xu, Yujun Chen, Yulun Du, Nan Shao, Yanggang Wang, Haiyu Li, and Zhilin Yang. 2022. Gps: Genetic prompt search for efficient few-shot learning. arXiv preprint arXiv:2210.17041. find
  28. J Zamfirescu-Pereira, Richmond Wong, Bjoern Hartmann, and Qian Yang. 2023. Why johnny can’t prompt: how non-ai experts try (and fail) to design llm prompts. In Proceedings of the 2023 CHI conference on human factors in computing systems (CHI’23). find
  29. Andy Zeng, Adrian Wong, Stefan Welker, Krzysztof Choromanski, Federico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vincent Vanhoucke, et al. 2022. Socratic models: Composing zero-shot multimodal reasoning with language. arXiv preprint arXiv:2204.00598. find our card
  30. Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E Gonzalez. 2023. Tempera: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Learning Representations. find
  31. Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2022. Large language models are human-level prompt engineers. arXiv preprint arXiv:2211.01910. find our card