PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yongchao Chen, Jacob Arkin, Yilun Hao, Yang Zhang, Nicholas Roy, Chuchu Fan

arXiv:2402.08702v4cs.CLcs.AIcs.HCcs.RO

TL;DR

Multi-step agent tasks require long, complex prompts whose errors and individual actions are difficult to evaluate. PROMST combines human-designed feedback rules with a learned score model to optimize prompts, and it reports improvements over baseline methods across 11 tasks and multiple LLMs.

  • Problem

    Multi-step agent prompts are longer and more complex than single-step prompts, making error analysis and evaluation of individual actions challenging.

    Source: §1 · p. 1

  • Method

    PROMST combines human-designed rules that generate error feedback with a learned score prediction model that selects prompt candidates for evaluation.

    Source: §3.2 · p. 4

  • Results

    10.6%-29.3% relative improvements over all baseline methods across different LLMs, with experiments spanning 11 tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors release code and prompts for 11 multi-step environments as a potential benchmark for automatic prompt optimization.

    Source: §1 · p. 2

    PROMST still requires substantial computing resources and LLM API queries, with around 100 prompt candidates explored despite score-model efficiency.

    Source: §6 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

PROMST addresses automatic prompt optimization for multi-step agent tasks, where long, complex prompts make error analysis and evaluation of individual actions difficult. It combines human-designed feedback rules with a learned score model to improve prompt search.

1 Introduction

  • Multi-step agent prompts are typically 300+ tokens and encode task constraints, making long-horizon correctness of individual actions difficult to judge.This difficulty hinders automatic error reasoning and prompt improvement.Source: §1 · p. 1
  • PROMST uses human-designed rules to generate error feedback for prompt candidates and an online score prediction model to select candidates for evaluation.Prompt-score pairs train the model, reducing the need to evaluate many costly candidates.Source: §1 · p. 2
  • 10.6%-29.3% relative improvements over all baseline methods across different LLMs, with PROMST achieving the best performance on most tasks.Experiments covered 11 tasks.Source: §1 · p. 2
  • PROMST is presented as the first exploration of automatic prompt optimization in multi-step agent tasks, with released code and prompts for 11 environments as a potential benchmark.The authors also report that human-designed evaluation rules help align optimized prompts with human preferences.Source: §1 · p. 2
  • PROMST integrates with established dynamic approaches, and its human-designed task evaluation rules help align optimized prompts with human preferences.The authors report these as contributions of the work.Source: §1 · p. 2

2 Related Work

Prior prompt optimization work uses gradient approximations, edit operators, and LLM-driven evolution, while LLM agents already tackle multi-step planning and feedback-based reflection. PROMST focuses on the more challenging multi-step setting, combining human feedback templates with score prediction.

2 Related Work

  • Prompt optimization methods approximate gradients, emulate them through natural language, use reinforcement-learning or score-guided edit operators, and apply LLM-driven evolution.Examples cited include Diao et al. (2022), Pryzant et al. (2023), Zhang et al. (2023), Prasad et al. (2023), Guo et al. (2023a), Fernando et al. (2023), Ma et al. (2023), and Ye et al. (2023).Source: §2 · pp. 2–3
  • Some prior methods generate prompt candidates directly with LLMs, often using feedback about parent prompts, whereas PROMST targets complex multi-step tasks with harder evaluation and reflection.The authors introduce score prediction and human feedback rules to address these challenges.Source: §2 · p. 3
  • LLM agents have been used for software and website interaction, robot action planning, and connecting to external tools; PROMST optimizes prompts from a simple initial prompt.The cited examples include Ma et al. (2024), Wu et al. (2023a), Zhou et al. (2023a), Chen et al. (2023b), and Qin et al. (2023).Source: §2 · p. 3
  • Prior feedback work addresses syntactic errors, loops, failed actions, and trajectories, while other studies use self-evaluation feedback for tasks including prompt engineering and reinforcement learning.PROMST combines LLM self-reflection with human-provided feedback templates for multi-step tasks.Source: §2 · p. 3
  • Unlike Reflexion’s multiple-trial online action-memory optimization for each test, PROMST optimizes prompts offline across tests and can combine with online Reflexion in multi-trial settings.The authors report that PROMST outperforms the offline variation of Reflexion.Source: §2 · p. 3

3 Methodology

PROMST formulates prompt optimization as maximizing a task score across testing trials. Its framework evaluates prompts through multi-step agent interactions, generates candidates from feedback, and uses a learned score model to reduce evaluation costs.

3.1 Problem Formulation

  • Prompt optimization seeks a natural-language prompt that maximizes a human-designed score over action sequences executed in the task environment.The prompt may include a task description, scoring rules, and safety constraints.Source: §3.1 · p. 3

3.2 PROMST Framework

  • PROMST uses TaskLLM to execute tasks and PromptLLM to generate new candidates from feedback about current prompt performance.A trial is one execution in a testing case, and the TaskLLM acts over multiple rounds with the current prompt and execution history.Source: §3.2 · pp. 3–4
  • A learned score prediction model filters generated candidates before evaluation, balancing broader prompt exploration against costly multi-step task evaluation.The model is a task-specific bidirectional Longformer-base fine-tuned online on prompt-score pairs collected during early iterations.Source: §3.2 · p. 4
  • The filtering rule accounts for predicted score, prediction variance, and testing error, and applies only when the model is sufficiently confident.High variance or error leads to conservative filtering; users can tune this conservativeness with hyper_M.Source: §3.2 · p. 4
  • Human-designed rules synthesize feedback when execution errors occur, covering shared error types such as syntax as well as task-specific errors.Figure 2 shows eight feedback-template examples, with blue text marking content specific to each error instance.Source: §3.2 · p. 4, Figure 2 · p. 5
  • Feedback wording variability has little impact on performance, and each task needs only two to four new error types because some types are reusable across tasks.Examples of shared error types include syntactic errors and getting stuck in a loop.Source: §3.2 · p. 4
  • Candidate generation summarizes selected feedback with SumLLM, then gives that summary to GenLLM to produce new prompts.Ten feedback instances are randomly selected to encourage diverse candidates and potentially surface more frequent errors.Source: §3.2 · p. 4

4 Experiments

Across 11 multi-step tasks, PROMST performs best on most tasks and outperforms PromptAgent on average across five LLMs. The experiments also examine its score model, feedback components, prompt transfer, and alignment with human preferences.

4.1 Environments

  • Evaluation covers 11 multi-step tasks, six iterative prompt-optimization baselines, and several LLM pairings, using task-progress scores based on completed subgoals or substeps.The tested tasks require reasoning across large discrete action spaces; the reported score is the ratio of completed to total subgoals or substeps.Source: §4.1 · p. 5, §4.2 · p. 5, §4.3 · pp. 5–6

4.4 Results and Analysis

  • Each LLM does best with prompts optimized on it, although prompts trained with GPT-3.5-0613 or GPT-4 still outperform human prompts when tested with another TaskLLM.PROMST also performs well when TaskLLM and PromptLLM are the same model.Source: §4.4 · p. 6
  • PROMST outperforms PromptAgent on average with GPT-3.5-0613 (0.27 vs 0.32), GPT-4 (0.61 vs 0.69), Claude-3-opus (0.36 vs 0.46), Open-Mixtral-8x7B (0.12 vs 0.15), and Mixtral-large (0.30 vs 0.34).PROMST performs best on most tasks; the cited tables cover the main task results and the evaluation of other LLMs.Source: §4.4 · p. 6, Table 1 · p. 7, Table 2 · p. 7
  • The score prediction model makes prompt search more efficient and effective, with faster convergence and better scores than search without the model.Filtered prompts have reliably low scores, and the best prompt usually appears at iterations 5 to 7.Source: §4.4 · pp. 6–7, Figure 4 · p. 6
  • Fine-tuning Longformer surpasses GPT-4 few-shot learning once the data number increases over 40, while GPT-4 few-shot performance does not improve as examples increase.Figure 5a compares score-prediction errors across increasing amounts of few-shot examples or training data.Source: Figure 5 · p. 7, §4.4 · p. 8
  • Human feedback raises scores across four tasks, and adding SumLLM improves performance on all three representative tasks.Varying the wording of feedback templates has little impact on PROMST performance.Source: Figure 5 · p. 7, §4.4 · p. 8, Table 4 · p. 8
  • Changing score-function formats aligns optimized prompts with human preferences, while ablations find scores decline when detailed prompt points are shortened.The prompt analysis also suggests that stronger prompts clearly list careful points one by one.Source: §4.4 · p. 8
  • PROMST outperforms the offline variation of Reflexion in prompt optimization and achieves enhanced performance when Reflexion is integrated in a multi-trial setting.Source: §4.4 · p. 8

5 Conclusion

PROMST combines human feedback, learned score prediction, and task-score modification to optimize prompts for complex multi-step agent tasks. It generally outperforms six representative baselines across 11 task environments and all five LLMs, and can be combined with existing dynamic approaches.

5 Conclusion

  • To address task complexity, long-horizon action evaluation, exploration cost, and preference alignment, PROMST integrates human feedback, learned score prediction, and task-score modification.Source: §5 · pp. 8–9
  • PROMST generally outperforms six representative baselines across 11 task environments and all five LLMs.Source: §5 · p. 9
  • PROMST is orthogonal and combinatorial to existing dynamic approaches.The discovered best prompts also have characteristics described as inspiring for better performance.Source: §5 · p. 9

6 Limitations

PROMST has several resource and user-effort limitations: prompt search still requires substantial API use, while its score model adds local computing demands and human feedback rules must be predefined.

  • Around 100 prompt candidates still impose a substantial exploration burden despite the score model making search more efficient.The authors also describe automatic prompt optimization as requiring significant computing resources and LLM API queries.Source: §6 · p. 9
  • Training extra score prediction models increases local-device computing demands, trading some API queries for on-device computation.Source: §6 · p. 9
  • Requiring users to design feedback rules adds burden, and automatic feedback remains future work.The authors connect this design choice to current LLMs’ difficulty summarizing and reflecting on multi-step errors.Source: §6 · p. 9
  • Fine-tuning the score model typically requires around 100 prompt-score pairs, which may be unsuitable if future search methods need fewer data points.Source: §6 · p. 9

A Types of human feedback for each task

Table 6 organizes human feedback by testing task and error type; Figure 2 presents the specific feedback content.

B Algorithms

PROMST records prompt trials and their feedback, then iteratively generates candidates using summarized feedback and prompt history. Its meta-prompts direct separate feedback-summarizing and prompt-generating steps.

B Algorithms

  • Each prompt trial is evaluated with the task and its feedback rules, then stored with its score, feedback, and ancestor prompts.The initial prompt and later new prompts are both processed through the feedback rules.Source: B Algorithms · p. 13
  • The algorithm fine-tunes five score models on the recorded data, with each model taking a prompt as input and predicting its score.Source: B Algorithms · pp. 13–14
  • Candidate selection uses predicted score, prediction variance, and predicted error against a threshold based on the best recorded score.Source: B Algorithms · p. 14
  • SumLLM summarizes each feedback type, and GenLLM uses the summary and prompt trajectory to generate a new prompt.The trajectory includes the prompts leading to the current prompt.Source: B Algorithms · p. 14

C Meta-prompts of SumLLM and GenLLM

D Description of environments for multi-step tasks

The experiments span 11 multi-step environments with varied reasoning and interaction demands. The generalization tables compare optimized prompts across TaskLLMs, while the paper uses task progress rather than task completion as its score.

D Description of environments for multi-step tasks

  • The 11 environments require logical, geometrical, scientific, and commonsense reasoning, spanning web browsing, household tasks, and interactive science tasks.WebArena supports multi-round browsing across four applications; ALFWorld uses household subgoals, and ScienceWorld requires navigation and tool use.Source: D Description of environments for… · p. 16
  • The robot environments test box movement, lifting with partial weight observability, and warehouse delivery under movement constraints.Source: D Description of environments for… · p. 16
  • The planning environments include ordered-goal navigation, block stacking, and package transport constrained by vehicle and city routes.Source: D Description of environments for… · pp. 16–17

E Generalization to different models for optimized prompts

  • Tables 7 and 8 test whether prompts optimized with GPT-3.5-0613 or GPT-4 retain better performance than initial prompts when run with other TaskLLMs.Table 7 uses prompts found by GPT-3.5-0613 and tests them with GPT-3.5-0301 and GPT-4; Table 8 reverses the optimization model and tests with GPT-3.5 variants.Source: Table 7 · p. 18, Table 8 · p. 18
  • Task completion scores are positively correlated with task progress scores but are lower and less sensitive, so the study uses task progress as its metric.Source: Table 9 · p. 19

G Extra ablation experiments of score models

The ablation compares prompt selection with and without score models. Across BoxLift, WareHouse, and GridWorld2, score-model-guided optimization finds better prompts in fewer iterations.

G Extra ablation experiments of score models

  • Across BoxLift, WareHouse, and GridWorld2, score-model-guided optimization finds better prompts with fewer iterations.The comparison is an ablation of score models for prompt selection.Source: Figure 6 · p. 19

H Efforts for designing human feedback rules

The feedback-rule study finds that wording variation has little effect, while removing the TaskLLM response or stuck-in-loop feedback reduces performance. Across BoxLift, BoxNet1, and BoxNet2, higher-scoring prompts also share some execution trends, with task-specific differences.

H Efforts for designing human feedback rules

  • For a new task, users are expected to design only 3–5 feedback templates, since several templates, such as syntax-error rules, are common across tasks.The authors describe the task-specific templates as typically intuitive and report that this effort can significantly improve task performance.Source: H Efforts for designing human feedback… · p. 20
  • The ablation compares original templates with GPT-4 paraphrases, random template variants, templates without the TaskLLM response, and templates without stuck-in-loop feedback.The original templates did not require trial-and-error iteration over possible versions.Source: H Efforts for designing human feedback… · p. 20
  • Removing the TaskLLM response or stuck-in-loop feedback reduces PROMST performance, while wording variability has little impact.Randomly sampling paraphrased templates generally improves performance; the authors suggest increased candidate diversity as a possible explanation.Source: H Efforts for designing human feedback… · p. 20

I Component changes in each environment

J The influence of score functions

PROMST can change its score function to better reflect user preferences, though the original score may decline slightly. The study highlights a tension between task scores and preferences for efficiency or safety.

J The influence of score functions

  • In the three examined tasks, execution steps rise with prompt scores, while BoxNet2 collision errors also gradually rise, conflicting with efficiency and safety preferences.The authors note that people may prioritize efficiency or collision avoidance in addition to task completion.Source: J The influence of score functions · p. 22
  • Adjusting the ratio in the modified score can substantially change its trend relative to the original score.The modified-score figures cover BoxLift and BoxNet2.Source: J The influence of score functions · p. 22, Figure 10 · p. 23, Figure 11 · p. 23
  • New prompts generally achieve higher modified scores than the original prompts, while their original scores decrease slightly.The authors interpret this as evidence that changing score functions can align prompt selection with human preferences.Source: J The influence of score functions · p. 22

K Explanability for better prompts

The analysis finds that longer prompts tend to score higher, while prompt perplexity has no clear correlation with score. It also finds that explicitly listing task constraints supports performance in BoxLift and GridWorld2.

K Explanability for better prompts

L Comparison and combination with Reflexion

The section compares PROMST with offline Reflexion prompt optimization and tests PROMST prompts with online Reflexion feedback. PROMST outperforms offline Reflexion, while online feedback further improves agent performance in multi-trial execution.

  • The comparison adapts Reflexion for offline prompt optimization by adding case-specific memory to the initial prompt, either directly or after LLM summarization.These variants use environment feedback without human factors.Source: L Comparison and combination with… · p. 26
  • Offline Reflexion 2's memory summarization mitigates the case-specificity and length limits of concatenated memories, but remains less effective than PROMST.Offline Reflexion 1 can include only 3–5 cases because each case's memory is lengthy.Source: L Comparison and combination with… · p. 26
  • Online Reflexion feedback further enhances agent performance with PROMST's best prompts in multi-trial execution, while PROMST outperforms Reflexion in offline prompt optimization.Source: L Comparison and combination with… · p. 26

M Human prompts and discovered best prompts for GPT-3.5-0613 and GPT-4 in all the 11 multi-step tasks

This section presents human-written and discovered best prompts across 11 multi-step tasks, with prompt examples and reported scores for GPT-3.5-0613 and GPT-4. These examples illustrate task-specific guidance for carrying out the tasks.

M Human prompts and discovered best prompts for GPT-3.5-0613 and GPT-4 in all the 11 multi-step tasks

  • The appendix lists initial human and discovered best prompts for GPT-3.5-0613 and GPT-4 across 11 tasks, but omits GPT-4’s BoxLift prompt and GPT-3.5-0613’s WareHouse prompt for stated score-related reasons.The optimized BoxLift prompt can easily achieve a full score of 1.0; discovered WareHouse prompts for GPT-3.5-0613 score near 0.0.Source: M Human prompts and discovered best… · p. 27
  • On Alfworld, the human prompt scores 0.075 with GPT-3.5-turbo-16k-0613 and 0.45 with GPT-4 as testing LLMs; the cited passages give no discovered-prompt score.The human prompt directs the model to use observed valid actions and objects and learn from prior action-observation history. The optimized guidance says to keep the goal at the forefront of decision-making.Source: M Human prompts and discovered best… · pp. 31–32
  • Alfworld’s best prompt for GPT-4 scores 0.57 with GPT-4 as the testing LLM.The prompt stresses goal-aligned choices, checking object presence and action validity, maintaining state awareness, and revising after failure.Source: M Human prompts and discovered best… · p. 33
  • Scienceworld’s human prompt scores 0.18 with GPT-3.5-turbo-16k-0613 and 0.70 with GPT-4 as the testing LLM.The prompt asks the agent to ground actions in observations and the current valid-action list, and to learn from action history.Source: M Human prompts and discovered best… · p. 34
  • Scienceworld’s best GPT-3.5-turbo-16k-0613 prompt scores 0.21 with that model as the testing LLM.Its guidance includes looking around before acting, checking inventory, validating commands, and adapting after unsuccessful actions.Source: M Human prompts and discovered best… · pp. 35–36
  • Scienceworld’s best GPT-4 prompt scores 0.81 with GPT-4 as the testing LLM.It instructs the agent to use observed objects and locations, verify actions against the valid-action list, adapt to feedback, and avoid unnecessary steps.Source: M Human prompts and discovered best… · pp. 37–38

BoxLift

  • The BoxLift human prompt scored 0.31 with GPT-3.5-turbo-16k-0613 and 0.92 with GPT-4 as testing LLMs.It frames the task as coordinating agents with different lifting capabilities to lift all boxes in as few steps as possible.Source: M Human prompts and discovered best… · p. 45
  • BoxLift’s best GPT-3.5-turbo-16k-0613 prompt scored 0.90 on that testing LLM.It specifies capacity checks, nonduplicated agent assignments, prioritization of boxes, and feedback-based avoidance of failed combinations.Source: M Human prompts and discovered best… · pp. 45–46

WareHouse

  • A further reported test-score pair is 0.0 with GPT-3.5-turbo-16k-0613 and 0.16 with GPT-4.The surrounding passages describe a WareHouse task in which mobile agents pick up boxes, move them to a target, and avoid collisions.Source: M Human prompts and discovered best… · pp. 46–47
  • The WareHouse best prompt for GPT-4 specifies legal pickup and movement actions, collision constraints, and feedback-based planning to minimize steps.It allows an agent without a box to move to the target to avoid obstructing others, while prohibiting agents from sharing a track-and-column position.Source: M Human prompts and discovered best… · pp. 47–48

Gridworld1

Gridworld2

M Human prompts and discovered best prompts for GPT-3.5-0613 and GPT-4 in all the 11 multi-step tasks

  • 0.60 was the Gridworld2 best-prompt score with GPT-4 as the testing LLM.The prompt requires sequence and position checks before collecting goals, obstacle-aware path planning, and adjusting after errors or unproductive actions.Source: M Human prompts and discovered best… · pp. 54–55
  • The Blocksworld human prompt scored 0.71 with GPT-4 and 0.19 with GPT-3.5-turbo-16k-0613 as the testing LLM.The human prompt briefly lists block-manipulation actions and restrictions, and asks the model to learn from previous steps and avoid action loops.Source: M Human prompts and discovered best… · p. 56
  • On Blocksworld, the best prompt scored 0.6 with GPT-3.5-turbo-16k-0613 as the testing LLM; its strategy calls for comprehensive state verification before each action to ensure all preconditions are met.Source: M Human prompts and discovered best… · p. 57
  • 0.95 was the Blocksworld best-prompt score with GPT-4 as the testing LLM.The prompt directs the model to evaluate the goal state, plan action sequences, verify preconditions, and analyze state changes and errors.Source: M Human prompts and discovered best… · p. 58
  • Logistics Score rose from 0.083 with the human prompt to 0.18 with the GPT-3.5-turbo-16k-0613 best prompt, and from 0.50 to 0.74 for GPT-4.The testing LLMs were GPT-3.5-turbo-16k-0613 and GPT-4, respectively.Source: M Human prompts and discovered best… · pp. 59–61
  • The human prompt asks the model to learn from previous steps, avoid repeating actions or action loops, and use a specified action format.Source: M Human prompts and discovered best… · p. 60
  • The GPT-3.5 best prompt specifies loading and movement preconditions, state changes, failure tracking, loop avoidance, and task decomposition.It also provides action formats and directs planning toward package destinations.Source: M Human prompts and discovered best… · pp. 60–61
  • The GPT-4 best prompt requires pre-action state verification, immediate state updates, shortest-route planning, and adaptation after failures.It also directs the model to avoid ineffective actions and ensure each action contributes to package delivery.Source: M Human prompts and discovered best… · pp. 61–62
Loading 2402.08702v4…