MPO: Boosting LLM Agents with Meta Plan Optimization

1 Introduction

• Implicit planning can hallucinate, while trajectory tuning requires retraining for each new agent and incurs substantial computational cost.Knowledge-based guidance can require extensive manual effort or have difficulty ensuring quality, potentially resulting in inconsistent performance improvements.Source: §1 · p. 1
• MPO uses abstract meta plans, decoupled from environmental details and complex trajectories, and iteratively improves them using environmental feedback.This is presented as an alternative to acquiring complex guidance through extensive manual effort or uncertain quality assurance.Source: §1 · pp. 1–2
• The meta planner is initialized from expert-trajectory meta plans, then refined using agent execution feedback and preference learning on plans associated with the highest and lowest completion rates.The trained planner can be detached and used by new agents without additional training costs.Source: §1 · p. 2
• Across three representative benchmarks, MPO significantly improves existing LLM agents, with at least a 5.6% average performance improvement across test tasks.The meta planner is also compatible with different agent training frameworks and can be inserted directly into task instructions.Source: §1 · p. 2
• Analysis reports increased average reward per action and improved task-completion efficiency, alongside gains in plan correctness, followability, and standardization.A lightweight meta planner can also guide more powerful agents.Source: §1 · p. 2

2 Task Formulation

• An agent’s task-planning trajectory consists of an instruction, successive actions, and environment observations; at each step, the agent selects an action based on the instruction and prior interaction history.The trajectory’s final reward represents the task completion rate.Source: §2 · p. 2
• A meta plan is high-level, natural-language guidance that outlines an abstract task-completion strategy decoupled from specific environmental details.The meta planner generates a plan from the task instruction, which is incorporated into the agent’s trajectory-generation process.Source: §2 · pp. 2–3

3 Method

• The method initializes a planner, evaluates meta-plan quality through exploration, then refines the planner with preference-based optimization.These stages are supervised fine-tuning initialization, Monte Carlo quality evaluation, and contrastive-pair DPO training.Source: §3 · p. 3

3.1 Supervised Fine-tuning Initialization

• MPO first builds a seed meta-plan dataset from expert trajectories, manually reviews the plans, removes trajectories, and uses supervised fine-tuning to initialize the planner.The resulting planner generates plans from task instructions without access to golden trajectories at inference.Source: §3.1 · p. 3

3.2 Meta Plan Quality Evaluation

• Instead of human- or model-annotated preferences, MPO evaluates plans by having an agent attempt each task repeatedly and scoring plans by the agent’s task completion rate.The paper uses Llama-3.1-8B-Instruct for evaluation and reports that plans evaluated with it generalize to agents based on other models.Source: §3.2 · p. 4

3.3 Meta Planner DPO Training

• MPO samples candidate plans, scores them with the exploration method, and uses the highest- and lowest-quality plans as DPO preference pairs, skipping tasks whose plans tie.DPO fine-tunes the planner to increase the likelihood of the preferred plan over the rejected plan.Source: §3.3 · p. 4

4.1 Experiment Settings

• The evaluation covers ScienceWorld, ALFWorld, and WebShop, spanning textual science experiments, embodied household tasks, and online web navigation.ScienceWorld and WebShop provide dense rewards from 0 to 1; ALFWorld uses binary task-completion rewards.Source: §4.1 · p. 4

4.2 Results

• Up to 40.5% average performance increase for the Llama-3.1-8B-Instruct-based agent; MPO-enhanced Llama-3.1-8B-Instruct-ETO achieves an average reward 3.5 higher than WKM.Across tasks and frameworks, Table 2 reports consistent improvement; on unseen ALFWorld tasks, GPT-4o’s success rate rises by 9.7 to 93.3.Source: Table 2 · p. 5, §4.2 · p. 6

4.1 Experiment Settings

• Experiments compare MPO guidance across untrained ReAct agents and trained agent frameworks, with test-set plans reused across agents and Average Reward as the primary metric.The evaluated trained frameworks include AgentTuning and ETO; evaluation also includes explicit-guidance methods KnowAgent and WKM.Source: §4.1 · pp. 5–6

4.2 Results

• On unseen ALFWorld tasks, MPO improves GPT-4o’s success rate by 9.7, reaching 93.3, and the authors report generalization to unseen ScienceWorld tasks as well.The unseen ScienceWorld and ALFWorld variations were not encountered by the meta planner.Source: §4.2 · p. 6

5.1 Ablation Study

• MPO optimization outperforms other meta-planner training methods and direct GPT-4o prompting on unseen ScienceWorld and ALFWorld test sets.The comparison suggests environment exploration and learning from comparisons help produce higher-quality meta plans.Source: §5.1 · p. 6, Table 3 · p. 6

5.2 How to Use Meta Plan?

• Task-instruction insertion performs best across agents and tasks, while insertion into the agent’s thought process performs worst.Other insertion positions cause larger drops in trained frameworks, where training data does not include meta plans.Source: §5.2 · p. 6, Table 4 · p. 6

5.3 Efficiency Analysis

• MPO significantly raises average reward per step over no meta plan and SFT-initialized plans, with larger gains on unseen tasks.Average reward per step is final reward divided by steps required, averaged across the test set.Source: §5.3 · p. 7, Figure 3 · p. 7

5.4 Effect on Agents with Scaling Parameters

• MPO improves performance across parameter sizes, with the largest gains among medium-sized agents, and the lightweight meta planner can guide stronger agents without retraining.Source: §5.4 · p. 7, Figure 4 · p. 7

5.5 Effect of Sampling Count on Performance

• Lower sampling counts reduce meta-plan quality, especially when task-trajectory count N is reduced, while gains from increasing N and M quickly saturate.The main experiments use N = M = 5 to balance sampling cost and performance gains.Source: §5.5 · pp. 7–8, Figure 5 · p. 7

5.6 What Makes a Good Meta Plan?

• MPO-optimized meta plans outperform SFT-initialized plans in correctness, followability, and standardization.The reported advantages in correctness and followability make it easier for agents to plan and execute tasks, leading to higher task completion rates.Source: §5.6 · p. 8, Figure 6 · p. 8

• Implicit planning can suffer from myopic reasoning and planning hallucinations, while trajectory-based training requires retraining for each new agent.Source: §6 · p. 8
• Explicit guidance methods may require manually designed templates or procedures, while automated knowledge synthesis cannot refine outputs through exploration and environmental feedback.Source: §6 · p. 8
• MPO provides automatically generated high-level abstract meta plans and refines their quality using feedback from task completion.Source: §6 · p. 8

• MPO combines abstract high-level meta-plan guidance with task-execution feedback to continuously improve meta-plan quality.Source: §7 · pp. 8–9
• Across three benchmarks, MPO consistently outperforms existing baselines and applies to agents across a wide range of parameter sizes.Source: §7 · p. 9

• The meta planner uses Llama-3.1-8B-Instruct, is constructed separately for each task, and uses simple sampling and Monte Carlo methods to build contrastive pairs.The authors suggest exploring other or smaller base models, unified multi-task planners, and MCTS sampling.Source: Limitations · p. 9

• The authors report compliance with the ACL Ethics Policy and no known ethical issues.Source: Ethics Statement · p. 9

• ScienceWorld tests scientific reasoning through text-based experiments drawn from elementary-school science curricula, with final reward based on completed subgoals.Source: A Dataset Details · p. 12
• The ScienceWorld original test set contains unseen task variations, while the original validation set is used to test seen scenarios.For example, training may involve boiling water while testing involves boiling lead.Source: A Dataset Details · p. 12
• ALFWorld household tasks require room exploration and commonsense reasoning; its seen and unseen sets assess in-distribution and out-of-distribution generalization, respectively.Source: A Dataset Details · p. 12
• WebShop simulates online shopping across 1.18 million real-world products, rewarding how well purchased item attributes and price match the instruction.Source: A Dataset Details · p. 12

B Success Rate

• All agents show consistent and significant success-rate improvements on ScienceWorld and ALFWorld after MPO-optimized meta plans are inserted.ScienceWorld success means reaching a predefined latent state, even when reward is below 1.0; ALFWorld success rate equals average final reward.Source: B Success Rate · p. 12

C Seed Meta Plans Quality Control

• Seed meta plans are quality-controlled for excessive detail, inapplicable manipulation types, and format errors, with negligible human effort relative to manual knowledge construction.GPT-4o generation settings and re-summarization address the first two issues; prompting extracts correctly formatted plans, and manual verification remains required.Source: C Seed Meta Plans Quality Control · p. 12

D Case Study

• In the ALFWorld case, SFT guidance sends the agent repeatedly toward an erroneous sidetable, while MPO gives an abstract pillow-search strategy that leads it to check the armchair.The MPO plan is decoupled from specific environmental details; the example uses Llama-3.1-8B-Instruct.Source: D Case Study · pp. 12, 14
• Tables 5 and 6 present average-reward and success-rate comparisons, respectively, for agents with MPO-optimized plans across two datasets.Source: Table 5 · p. 13, Table 6 · p. 13

E.1 Prompt for Seed Meta Plans Collection

• The collection prompt supplies task instructions, environmental information, and the current trajectory so GPT-4o can extract a meta plan with environmental priors.The prompts for this process are shown for ScienceWorld, ALFWorld, and WebShop.Source: §E.1 · p. 14, Figure 7 · p. 16, Figure 8 · p. 16

E.2 Prompt for Evaluation

• Evaluation uses distinct instruction prompts for ScienceWorld, ALFWorld, and WebShop.Source: §E.2 · p. 14, Figure 10 · p. 18, Figure 11 · p. 19

E.3 Prompt for GPT Automated Assessment

• The automated assessment prompt compares meta-plan sets on correctness, followability, and standardization, then gives an overall assessment.Correctness concerns fulfilling task requirements; followability covers clarity and reasonableness of steps, and standardization checks consistent format.Source: §E.3 · p. 14, Figure 13 · p. 20
• The assessment prompt asks for an abstract, reusable step-by-step meta plan based on a task-solving conversation.Source: §E.3 · p. 15