# PRompt Optimization in Multi-Step Tasks (PROMST): Integrating Human Feedback and Heuristic-based Sampling

arXiv: https://arxiv.org/abs/2402.08702 · HTML: https://mlsanity.com/paper/2402.08702/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2024.

## Built on by (most cited first, 30 of 32)

- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [Direct Multi-Turn Preference Optimization for Language Agents](https://mlsanity.com/paper/2406.14868/) (2024)
- [Efficient Prompting Methods for Large Language Models: A Survey](https://mlsanity.com/paper/2404.01077/) (2024)
- [Self-Supervised Prompt Optimization](https://mlsanity.com/paper/2502.06855/) (2025)
- [Efficient and Accurate Prompt Optimization: the Benefit of Memory in Exemplar-Guided Reflection](https://mlsanity.com/paper/2411.07446/) (2024)
- [System Prompt Optimization with Meta-Learning](https://mlsanity.com/paper/2505.09666/) (2025)
- [MAPRO: Recasting Multi-Agent Prompt Optimization as Maximum a Posteriori Inference](https://mlsanity.com/paper/2510.07475/) (2025)
- [RePrompt: Planning by Automatic Prompt Engineering for Large Language Models Agents](https://mlsanity.com/paper/2406.11132/) (2024)
- [Fearful Falcons and Angry Llamas: Emotion Category Annotations of Arguments by Humans and LLMs](https://mlsanity.com/paper/2412.15993/) (2024)
- [CodeSteer: Symbolic-Augmented Language Models via Code/Text Guidance](https://mlsanity.com/paper/2502.04350/) (2025)
- [Code-as-Symbolic-Planner: Foundation Model-Based Robot Planning via Symbolic Code Generation](https://mlsanity.com/paper/2503.01700/) (2025)
- [Generalizability of Large Language Model-Based Agents: A Comprehensive Survey](https://mlsanity.com/paper/2509.16330/) (2025)
- [LLM Prompt Duel Optimizer: Efficient Label-Free Prompt Optimization](https://mlsanity.com/paper/2510.13907/) (2025)
- [SIPDO: Closed-Loop Prompt Optimization via Synthetic Data Feedback](https://mlsanity.com/paper/2505.19514/) (2025)
- [What Makes a Good Natural Language Prompt?](https://mlsanity.com/paper/2506.06950/) (2025)
- [A Survey of Automatic Prompt Optimization with Instruction-focused Heuristic-based Search Algorithm](https://mlsanity.com/paper/2502.18746/) (2025)
- [Large Language Models and Evolutionary Computation: A Critical Review of Bidirectional Interaction, Automated Algorithm Design, and Co-Adaptive Systems](https://mlsanity.com/paper/2505.15741/) (2025)
- [Adaptive Prompt Structure Factorization: A Framework for Self-Discovering and Optimizing Compositional Prompt Programs](https://mlsanity.com/paper/2604.06699/) (2026)
- [GREATERPROMPT: A Unified, Customizable, and High-Performing Open-Source Toolkit for Prompt Optimization](https://mlsanity.com/paper/2504.03975/) (2025)
- [AEGIS : Automated Co-Evolutionary Framework for Guarding Prompt Injections Schema](https://mlsanity.com/paper/2509.00088/) (2025)
- [LLM-Driven Self-Refinement for Embodied Drone Task Planning](https://mlsanity.com/paper/2508.15501/) (2025)
- [QueryBandits for Hallucination Mitigation: Exploiting Semantic Features for No-Regret Rewriting](https://mlsanity.com/paper/2508.16697/) (2025)
- [Beyond Elicitation: Provision-based Prompt Optimization for Knowledge-Intensive Tasks](https://mlsanity.com/paper/2511.10465/) (2025)
- [UPA: Unsupervised Prompt Agent via Tree-Based Search and Selection](https://mlsanity.com/paper/2601.23273/) (2026)
- [The Horizon Gap: Planning, Memory, Execution, Training, and Evaluation for Long-Horizon LLM Agents](https://mlsanity.com/paper/2608.06663/) (2026)
- [Do Self-Evolving Skills Generalize to Held-Out Tasks?](https://mlsanity.com/paper/2609.39148/) (2026)
- [Synthetic Data-Driven Prompt Tuning for Financial QA over Tables and Documents](https://mlsanity.com/paper/2511.06292/) (2025)
- [No One Size Fits All: QueryBandits for Hallucination Mitigation](https://mlsanity.com/paper/2602.20332/) (2026)
- [Context-Mediated Domain Adaptation in Multi-Agent Sensemaking Systems](https://mlsanity.com/paper/2603.24858/) (2026)
- [Towards Spec Learning: Inference-Time Alignment from Preference Pairs](https://mlsanity.com/paper/2606.24004/) (2026)

## Abstract (arXiv)

Prompt optimization aims to find the best prompt to a large language model (LLM) for a given task. LLMs have been successfully used to help find and improve prompt candidates for single-step tasks. However, realistic tasks for agents are multi-step and introduce new challenges: (1) Prompt content is likely to be more extensive and complex, making it more difficult for LLMs to analyze errors, (2) the impact of an individual step is difficult to evaluate, and (3) different people may have varied preferences about task execution. While humans struggle to optimize prompts, they are good at providing feedback about LLM outputs; we therefore introduce a new LLM-driven discrete prompt optimization framework PRompt Optimization in Multi-Step Tasks (PROMST) that incorporates human-designed feedback rules to automatically offer direct suggestions for improvement. We also use an extra learned heuristic model that predicts prompt performance to efficiently sample from prompt candidates. This approach significantly outperforms both human-engineered prompts and several other prompt optimization methods across 11 representative multi-step tasks (an average 10.6%-29.3% improvement to current best methods on five LLMs respectively). We believe our work can serve as a benchmark for automatic prompt optimization for LLM-driven multi-step tasks. Datasets and Codes are available at https://github.com/yongchao98/PROMST. Project Page is available at https://yongchao98.github.io/MIT-REALM-PROMST.