CoChat
Sign Up
PreprintCited by 191Topic ModelingNatural Language Processing TechniquesDomain Adaptation and Few-Shot Learning

Automatic Prompt Optimization with "Gradient Descent" and Beam Search

Open access
Pryzant, Reid, Iter, Dan, Li, Jerry, Lee, Yin Tat, Zhu, Chenguang, Zeng, Michael·2023·arXiv
DOI 10.48550/arxiv.2305.03495arXiv 2305.03495
Open this paper in CoChat — free accountOpen PDF

Abstract

Large Language Models (LLMs) have shown impressive performance as general purpose agents, but their abilities remain highly dependent on prompts which are hand written with onerous trial-and-error effort. We propose a simple and nonparametric solution to this problem, Automatic Prompt Optimization (APO), which is inspired by numerical gradient descent to automatically improve prompts, assuming access to training data and an LLM API. The algorithm uses minibatches of data to form natural language "gradients" that criticize the current prompt. The gradients are then "propagated" into the prompt by editing the prompt in the opposite semantic direction of the gradient. These gradient descent steps are guided by a beam search and bandit selection procedure which significantly improves algorithmic efficiency. Preliminary results across three benchmark NLP tasks and the novel problem of LLM jailbreak detection suggest that Automatic Prompt Optimization can outperform prior prompt editing techniques and improve an initial prompt's performance by up to 31%, by using data to rewrite vague task descriptions into more precise annotation instructions.

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

DataCite · 10.48550/arxiv.2305.03495

Cites

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?

  • Existing automatic prompt optimization frameworks optimize almost exclusively for task accuracy, often at the expense of generating excessively verbose intermediate reasoning traces.

    “Existing automatic prompt optimization(APO) frameworks target task accuracy exclusively at the expense of generating long reasoning traces.”

    From CROP: Token-Efficient Reasoning in Large Language Models via Regularized Prompt Optimization (2026) · cites this paper as Pryzant et al., 2023

    The Setup (section 3.2; page not provided) says this paper optimized F1 score, an accuracy-related metric. It also notes that other work used log-likelihood, so it does not establish that existing frameworks target accuracy exclusively. Neither that section nor the retrieved passages link prompt optimization to long intermediate reasoning traces. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • In content generation, prompt engineering can be adopted to refine inputs to achieve better performance and higher quality results.

    “Therefore, prompt engineering [147, 148] can be adopted to refine these inputs to achieve better performance and higher quality results.”

    From Human-inspired Perspectives: A Survey on AI Long-term Memory (2024) · cites this paper as [147]

    Section 2 describes refining an initial prompt to improve a chosen performance metric, and the Overall Results report improved performance. However, Section 3.1 says the experiments covered four classification tasks, not content generation; the paper mentions summarization only as a possible application. It does not establish higher-quality generated content. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • Pryzant et al. use a workingout-conditioned error detection and error fixing prompt to improve the task specification prompt, a self-referential process similar to our use of the Lamarckian operator.

    “Pryzant et al use a workingout-conditioned error detection and error fixing prompt to improve the task specification prompt, a self-referential process similar to our use of the Lamarckian operator.”

    From Promptbreeder: Self-Referential Self-Improvement via Prompt Evolution (2023) · cites this paper as Pryzant et al., 2023

    Section 2.2.1 (page unavailable) describes using a prompt to identify problems behind observed errors, then a second prompt to edit the task prompt in a recursive feedback loop. The appendix’s “Generating gradients” section shows that these prompts use the current prompt and examples it gets wrong; our copy does not establish that they are conditioned on a “workingout.” (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • By integrating Shapley value-based attribution with automated prompt optimization techniques, CG-OPO addresses fundamental system bottlenecks, enabling scalable autonomous improvement in DAG-structured multi-agent architectures.

    “By integrating Shapley value-based attribution with automated prompt optimization techniques (Li et al. 2025; Pryzant et al. 2023), CG-OPO addresses fundamental system bottlenecks, enabling scalable autonomous improvement in DAG-structured multi-agent architectures”

    From HiveMind: Contribution-Guided Online Prompt Optimization of LLM Multi-Agent Systems (2025) · cites this paper as Pryzant et al. 2023

  • Researchers are starting to apply discrete optimization and RL to find effective prompts, generally for a single logical LM call.

    “Researchers are starting to apply discrete optimization and RL to find effective prompts, generally for a single logical LM call (Guo et al., 2023; Pryzant et al., 2023; Huang et al., 2022; Yang et al., 2023).”

    From DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines (2023) · cites this paper as Pryzant et al., 2023

Self-check

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

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

The citation lists haven’t been fetched yet

References 29 · Cited by 191

Research works printed but not linked: 30

  1. Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. 2010. Best arm identification in multi-armed bandits. In COLT, pages 41-53.
  2. Steven Bird. 2006. Nltk: the natural language toolkit. In Proceedings of the COLING/ACL 2006 Interactive Presentation Sessions, pages 69-72.
  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.
  4. Sébastien Bubeck, Varun Chandrasekaran, Ronen El- dan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lund- berg, et al. 2023. Sparks of artificial general intelli- gence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712. · arXiv
  5. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128. · arXiv
  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. · arXiv
  7. Ibrahim Abu Farha and Walid Magdy. 2020. From arabic sentiment analysis to sarcasm detection: The arsarcasm dataset. In Proceedings of the 4th Work- shop on Open-Source Arabic Corpora and Process- ing Tools, with a Shared Task on Offensive Language Detection, pages 32-39.
  8. Tianyu Gao, Adam Fisch, and Danqi Chen. 2020. Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012.15723. · arXiv
  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
  10. Karen Hambardzumyan, Hrant Khachatrian, and Jonathan May. 2021. Warp: Word-level adversarial reprogramming. arXiv preprint arXiv:2101.00121. · arXiv
  11. Yaru Hao, Zewen Chi, Li Dong, and Furu Wei. 2022. Optimizing prompts for text-to-image generation. arXiv preprint arXiv:2212.09611. · arXiv
  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. · arXiv
  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 Ab- stracts, pages 1-8.
  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.
  15. Volodymyr Kuleshov and Doina Precup. 2014. Al- gorithms for multi-armed bandit problems. arXiv preprint arXiv:1402.6028. · arXiv
  16. Brian Lester, Rami Al-Rfou, and Noah Constant. 2021. The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691. · arXiv
  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.
  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. · arXiv
  19. Ioannis Mollas, Zoe Chrysopoulou, Stamatis Karlos, and Grigorios Tsoumakas. 2020. Ethos: an on- line hate speech detection dataset. arXiv preprint arXiv:2006.08328. · arXiv
  20. Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2022. Grips: Gradient-free, edit-based in- struction search for prompting large language models. arXiv preprint arXiv:2203.07281. · arXiv
  21. Guanghui Qin and Jason Eisner. 2021. Learning how to ask: Querying lms with mixtures of soft prompts. arXiv preprint arXiv:2104.06599. · arXiv
  22. Laria Reynolds and Kyle McDonell. 2021. Prompt pro- gramming for large language models: Beyond the few-shot paradigm. In Extended Abstracts of the 2021 CHI Conference on Human Factors in Comput- ing Systems, pages 1-7.
  23. 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. · arXiv
  24. William Yang Wang. 2017. " liar, liar pants on fire": A new benchmark dataset for fake news detection. arXiv preprint arXiv:1705.00648. · arXiv
  25. Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Al- isa Liu, Noah A Smith, Daniel Khashabi, and Han- naneh Hajishirzi. 2022. Self-instruct: Aligning lan- guage model with self generated instructions. arXiv preprint arXiv:2212.10560. · arXiv
  26. Hanwei Xu, Yujun Chen, Yulun Du, Nan Shao, Yang- gang Wang, Haiyu Li, and Zhilin Yang. 2022. Gps: Genetic prompt search for efficient few-shot learning. arXiv preprint arXiv:2210.17041. · arXiv
  27. J Zamfirescu-Pereira, Richmond Wong, Bjoern Hart- mann, and Qian Yang. 2023. Why johnny can't prompt: how non-ai experts try (and fail) to de- sign llm prompts. In Proceedings of the 2023 CHI conference on human factors in computing systems (CHI'23).
  28. Andy Zeng, Adrian Wong, Stefan Welker, Krzysztof Choromanski, Federico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vin- cent Vanhoucke, et al. 2022. Socratic models: Com- posing zero-shot multimodal reasoning with lan- guage. arXiv preprint arXiv:2204.00598. · arXiv
  29. Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schu- urmans, and Joseph E Gonzalez. 2023. Tempera: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Learn- ing Representations.
  30. 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. · arXiv

Authors
Pryzant, R., Iter, D., Li, J., Lee, Y. T., Zhu, C., & Zeng, M.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
Pages
7957-7968
DOI
10.48550/arxiv.2305.03495
arXiv
2305.03495
OpenAlex
W4389520756
Cited by
191
References
29
Citations by year
2026: 71 · 2025: 79 · 2024: 30 · 2023: 11
FWCI
33.91
Type
conference paper
Language
en
Open access
Licence
Locations
  • Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
Keywords
large language models, gradient descent, beam search

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