RePrompt: Planning by Automatic Prompt Engineering for Large Language Models Agents

1 Introduction

• Prompt variations can produce dramatically different success rates, while manual prompt engineering is challenging and time-intensive.Prior automatic prompt engineering can efficiently find robust prompts that outperform simple initial prompts.Source: §1 · p. 1
• Existing automatic prompt engineering depends on repeatedly checking prompt performance, but accurate final evaluators can be costly or absent in agent applications.Without cheap evaluators, existing methods cannot be applied in these scenarios.Source: §1 · p. 2
• RePrompt uses dialogue histories from interactions and reflections to update step-by-step instructions without a ground-truth checker.It summarizes the histories and analyzes how to improve the prompt step by step while avoiding overfitting to corner cases.Source: §1 · p. 2
• The paper evaluates RePrompt on PDDL generation, TravelPlanner, and Meeting Planning, reporting higher first-round success rates.The authors also state that the method can be combined with different types of feedback generators.Source: §1 · p. 2

2 Related Works

• Prompt optimization includes differentiable soft-prompt tuning, auxiliary optimizer models, direct prompter training, feedback-based methods, and beam or Monte Carlo tree search.Several approaches require access to language-model weights, limiting applicability when models are used through APIs.Source: §2 · p. 3
• RePrompt is presented as a generalization of feedback-based prompt-optimization methods to reasoning domains that does not require ground-truth feedback.The authors frame this setting as aligned with LLM-agent applications such as GPTs OpenAI [2023b].Source: §2 · p. 3
• Reasoning approaches use CoT, tree- or graph-structured thoughts, and interaction methods such as REACT and REFLEXION to guide model outputs.Other feedback-guided approaches include self-refine, RCI, and self-debugging.Source: §2 · p. 3

3.2.1 Overview

• RePrompt targets known LLM-agent planning tasks where the final solution checker is unavailable because of its cost.Agent feedback may include error messages, and checking prompt quality can be expensive or infeasible in some settings.Source: §3.1 · pp. 3–4, §3.2.1 · p. 4
• The Actor generates responses on a small training dataset using the current prompt and an interaction scheme with a feedback generator.The method imposes no constraint on how that interaction is performed or how accurate its feedback is.Source: §3.2.1 · p. 4
• A summarizer processes a complete batch of chat histories to identify recurring issues or effective suggestions while omitting scenario-specific details.The optimizer then proposes and selects a solution, deciding whether to add it as a step, insert it before a step, or replace a step.Source: §3.2.1 · pp. 4–5
• The optimizer favors common structural guidance over scenario-specific details and prioritizes a problem only when it occurs in the given scenario.For a suspected budget issue, it first approximates a typical plan's cost and prioritizes the constraint only if the plan breaks it.Source: §3.2.1 · p. 4
• Iterations continue until the prompt converges; testing then uses the updated prompt, and the feedback generator can be removed if expensive.The authors describe the optimization loop as analogous to machine-learning training, with prompts as parameters and LLMs serving as loss and optimizer.Source: §3.2.1 · pp. 4–5
• RePrompt changes step-by-step instructions rather than other prompt content, refining existing reasoning hints or incrementally adding steps.The process starts from the original prompt; when needed, an auxiliary checker helps structure it into analysis and solution steps, and examples remain unchanged because updating them consistently is difficult.Source: §3.2.1 · p. 5

4.1 Experiment Settings

• The three benchmarks pair RePrompt with distinct feedback: expert/LLM checking for PDDL, REFLEXION for TravelPlanner, and DeepSeek-R1 thinking for Meeting Planning.PDDL feedback is accurate but expensive, while TravelPlanner feedback is cheap but not accurate.Source: §4.1 · p. 6

4.2 PDDL Generation

• After one epoch, RePrompt improves PDDL success rates on Tyreworld and related domains, with new-prompt errors remaining a subset of the original prompt’s errors.The evaluation covers initial precondition and effect generation, not later correction or translation phases; expert feedback is accurate but expensive.Source: §4.2 · pp. 6–7

4.3 TravelPlanner

• After five epochs, RePrompt beats REFLEXION and PromptAgent in TravelPlanner final pass rate and improves performance on both training and held-out data.The prompt after one epoch showed no benefit; the five-epoch result is reported for the validation set.Source: §4.3 · pp. 7–8, Table 2 · p. 7

4.4 Ablation Study

• With the training budget fixed at 50 sample-epochs, RePrompt’s performance depends on balancing sample diversity against the number of optimization epochs.A training sample count of one reduces the method to a prompt optimizer without per-scenario summarization.Source: §4.4 · p. 8, Table 3 · p. 8

4.5 Meeting Planning

• Despite highly noisy thinking logs, RePrompt improves the original prompt on Meeting Planning using DeepSeek-R1.Training uses the first nine data points with batch size three, and evaluation uses the first 100.Source: §4.5 · p. 9, Table 4 · p. 9

5 Error Analysis

• The optimizer does not guarantee an improved prompt, and the section presents its interventions as pragmatic solutions to specific issues rather than universal fixes.The authors expect these interventions may become obsolete as instruction-following improves.Source: §5 · p. 9

5.1 Incomplete Prompt

• The experiments used a subset of the dataset because Deepseek-R1 availability was limited when they were conducted.The passage is a footnote and does not describe an error-handling strategy.Source: §5.1 · p. 9
• The optimizer may return a template with example placeholders instead of a complete prompt, requiring post-processing with the original prompt.The authors report this failure for both RePrompt and PromptAgent; it is more frequent with relatively long initial prompts, and they use an additional LLM to complete templates.Source: Figure 2 · p. 9, §5.1 · p. 10

5.2 Incorrect Change by Accident

• In PDDL tasks, an accidental capitalization change from “Preconditions” to “precondition” can break answer extraction, so the syntax checker triggers RePrompt to rerun that step.The authors report the failure rate of this ad hoc solution as empirically below 10%.Source: §5.2 · p. 10

• RePrompt summarizes agent interactions and feedback-generator outputs to optimize step instructions in prompts.Source: §6 · p. 10
• Across three challenging reasoning tasks, agents could benefit from updated prompts regardless of feedback type and without a ground-truth checker.The authors note that performance remains limited by the natural capability of the feedback-generation loop.Source: §6 · p. 10

• Prompts optimized on training data may generalize less well and can be less efficient than original prompts when training examples contain scenario-specific challenges.Source: A Limitations · p. 14
• RePrompt may suggest tools unavailable to the agent because its generated methods are not filtered through a search-based process.The authors leave having the LLM code such additional tools to future work.Source: A Limitations · p. 14
• Useless or misleading feedback may be incorporated into prompts, increasing token use without improving results because RePrompt does not remove useless steps.A proposed search-based correction could require more ground-truth feedback and narrow applicability.Source: A Limitations · p. 14
• Prompt-phase planning will not work for very general domains whose scenarios require completely different procedures, though the authors say it could help specific tasks.They contrast general math problem-solving with high-school geometry.Source: A Limitations · p. 14

• The TravelPlanner environment did not provide PromptAgent’s usual boolean ground-truth checker during APE, so the authors added an LLM-based checker after each completed reflection run.The checker received the same input as the plan generator and the generated plan.Source: §B.1 · p. 14
• In TravelPlanner, the adapted LLM checker had 89% accuracy, but plans succeeded at under 5%, so always marking plans incorrect would perform better overall.The authors observed hallucinations and false negatives; five false negatives tested with GPT-4o were all correct, but they retained GPT-4-turbo for consistency.Source: §B.1 · p. 14
• The authors modified the gradient-descent prompt template to remove its requirement for ground-truth labels, which were unavailable in their setting.Source: §B.1 · p. 14
• PromptAgent-Lite remained about twice as expensive as RePrompt despite limiting iterations for a fair comparison.Source: §B.1 · p. 14

• The dataset provides prompts for both 0-shot and 5-shot settings.Source: §B.2 · p. 15
• The original checker supports only the 5-shot output format, while the experiment uses the 0-shot prompt in keeping with Deepseek-R1 guidance.Source: §B.2 · p. 15
• Deepseek-V3 transforms collected 0-shot solutions into the desired Natural Plan format, a process that may turn some correct responses into incorrect ones.Source: §B.2 · p. 15, Figure 3 · p. 15

C Pseudo Code for REPROMPT

• The pseudocode frames prompt optimization as a training loop analogous to a typical machine-learning loop.Source: C Pseudo Code for REPROMPT · p. 15
• RePrompt’s training loop initializes a prompt, acts on each batch, summarizes loss, updates the prompt, and returns the optimized prompt.Source: C Pseudo Code for REPROMPT · p. 15

D Prompts for REPROMPT

• The appendix lists prompts for loss summarization, prompt optimization, and replacing accidental placeholders.Source: D Prompts for REPROMPT · p. 15

E Optimized Prompt from RePrompt

• OpenAI API outputs are not guaranteed to repeat exactly under identical settings, and reported results are the best of three trials.The authors say this variability affects final results; they also report that the relative superiority of RePrompt held in their experiments.Source: E Optimized Prompt from RePrompt · p. 17
• The appendix provides optimized prompts for PDDL generation, TravelPlanner, and Meeting Planning, plus a PromptAgent-generated TravelPlanner prompt.The prompts are shown in Figures 8–12.Source: E Optimized Prompt from RePrompt · p. 17, Figure 8 · p. 18, Figure 9 · p. 18
• The supplied task prompts cover PDDL action generation, TravelPlanner planning, and a Meeting Planning task focused on meeting as many friends as possible.Source: E Optimized Prompt from RePrompt · pp. 18–19
• TravelPlanner prompts are shown after one and five RePrompt epochs, while the Meeting Planning prompt is shown after five epochs.Source: Figure 9 · p. 18, Figure 10 · p. 19, Figure 11 · p. 20