PaperlayerView exact revision on arXiv

Source-linked AI summary

MOAE: Multi-Objective Agent Evolution with Pareto-Preserving Search

Hengle Jiang, Qijun Cai, Ziying Luo, Ke Tang

arXiv:2609.05992v1cs.AIcs.LG

TL;DR

Agent objectives such as task success, trajectory quality, and safety can conflict, while fixed scalarization may discard useful trade-offs. MOAE preserves non-dominated rollout candidates during limited-budget search and applies deployment constraints afterward; experiments report improvements across TravelPlanner and AgentDojo, with stated limits from evaluators and candidate budgets.

  • Problem

    Agent properties such as task performance, trajectory quality, and safety can conflict, while fixed scalarization depends on normalization and preference weights that may discard useful deployment trade-offs.

    Source: Introduction · p. 1

  • Method

    MOAE uses limited-budget in-context evolution to preserve an empirical archive of non-dominated rollouts, guide offspring with objective-specific diagnostics, and select a candidate under deployment constraints.

    Source: Introduction · p. 2, Multi-Objective Agent Evolution · p. 4

  • Results

    Across three execution models on TravelPlanner, MOAE improves task performance, trajectory quality, and safety risk; on AgentDojo it improves utility and trajectory quality while eliminating the observed attack success.

    Source: Conclusion · p. 7

  • Takeaways & Limitations

    Pareto preservation keeps specialized and balanced candidates available so deployment constraints, rather than one search-time weight configuration, determine the final choice.

    Source: Conclusion · p. 7

    MOAE remains bounded by evaluator quality and candidate budget, uses a small empirical non-dominated archive rather than a global Pareto-front approximation, and adds inference overhead.

    Source: Conclusion · p. 7

Abstract

from arXiv · show

As LLM-based agents continue to advance, their evaluation has become increasingly multifaceted: a capable agent must not only achieve high task completion accuracy but also perform well in interaction quality, safety, and efficiency, raising a central question: can these objectives be optimized simultaneously? Existing methods have considered multiple objectives, but many collapse heterogeneous measurements into a fixed scalar score. Such scalarization depends on metric normalization and preference weights and may discard candidates that represent useful deployment trade-offs. We introduce Multi-Objective Agent Evolution (MOAE), which organizes iterative in-context refinement as a Pareto-preserving evolutionary search over complete agent rollouts. Given a limited rollout budget, MOAE maintains an empirical archive of non-dominated candidates, uses objective-specific diagnostics to guide offspring generation, and applies constraint-aware selection only at deployment. This separates candidate preservation during search from the preference used to return a final solution. The procedure requires no parameter updates and allows each objective to be replaced by any measurable property, which we instantiate as task performance, trajectory quality, and safety. Experiments on TravelPlanner and AgentDojo show that MOAE consistently improves task performance and trajectory quality while maintaining strong safety under matched rollout budgets. Search-behavior analysis further shows that Pareto preservation expands the attainable objective region and increases the frequency of joint improvement. These results demonstrate the potential of Pareto-preserving in-context evolution for optimizing multiple agent properties without committing to a fixed scalarization during search.

Introduction

LLM agents require evaluation beyond final-answer accuracy because task success, trajectory quality, safety, and operational cost can conflict. MOAE addresses the limited-budget, per-query setting by preserving rollout trade-offs during search and applying deployment preferences only when selecting a candidate.

Introduction

  • Agent quality spans task completion, grounded trajectories, safety, and operational cost, and improvements on these dimensions may conflict.More tool use can improve evidence coverage while adding redundant or invalid actions; conservative behavior can reduce safety risk while limiting exploration.Source: Introduction · p. 1
  • Existing approaches commonly encode trade-offs through fixed scalarization or predefined preferences, while limited-budget per-query preservation of rollout-level trade-offs has received less attention.Fixed scalarization requires normalization and preference weights that can discard candidates useful under another deployment requirement.Source: Introduction · p. 1
  • MOAE keeps the model, tools, and agent architecture fixed while evolving execution policies through complete rollouts, an empirical non-dominated archive, and diagnostic-guided mutation.It separates candidate preservation during search from constraint-aware deployment selection.Source: Introduction · pp. 1–2
  • Matched-budget evaluations on TravelPlanner and AgentDojo examine final performance and search behavior across three language models and multiple baselines.Ablations isolate mutation, diagnostics, and the non-dominated archive.Source: Introduction · p. 2

Related Work

Prior work evaluates multiple aspects of agent behavior and optimizes pairs of objectives or reusable artifacts. MOAE instead studies limited-budget, per-query optimization that preserves rollout-level trade-offs and defers preference selection to deployment.

LLM Agent Evaluation

  • Agent benchmarks assess distinct properties such as task completion, interaction progress, planning validity, tool use, efficiency, and safety, but do not specify how to improve several measured properties jointly.TravelPlanner tests long-horizon planning constraints, while InjecAgent and AgentDojo examine utility under indirect prompt injection.Source: LLM Agent Evaluation · p. 2

Pairwise Objective Optimization in LLMs and Agents

  • Prior multi-objective methods commonly optimize predefined pairs, such as helpfulness and harmlessness or accuracy and inference efficiency, using constrained learning, preferences, or objective-specific structures.MOAE addresses a complementary setting: heterogeneous outcomes measured after complete rollouts, preserved under a limited per-query budget, with preferences applied at deployment.Source: Pairwise Objective Optimization in… · p. 2

LLM Agent Evolution

  • Existing evolutionary approaches mainly optimize reusable prompts, programs, agent architectures, or skills across development tasks, whereas MOAE optimizes a fixed agent per query and separates search from deployment selection.Some prior approaches already use Pareto-based selection or consider capability and safety, but target reusable artifacts or skill bundles.Source: LLM Agent Evolution · p. 2

Method

MOAE treats per-query refinement as a multi-objective evolutionary search over complete rollouts, preserving non-dominated candidates rather than collapsing them into one score. It uses objective-specific diagnostics to generate offspring and applies deployment preferences after search.

Method

  • MOAE starts from a default execution policy, evaluates complete rollouts on multiple objectives, preserves empirical non-dominated candidates, and selects one candidate by a deployment preference after the rollout budget is spent.The workflow uses model inference and in-context feedback without updating agent or mutation-model parameters.Source: Method · pp. 2–3

Problem Formulation

  • A candidate packages an execution policy, its complete rollout, objective values, and evaluator diagnostics.Diagnostics can capture constraint violations, unsupported decisions, invalid actions, and repeated tool calls.Source: Problem Formulation · p. 3
  • The problem assumes objectives are computable from completed rollouts and seeks to preserve candidates with different trade-offs under a limited online budget.The formulation does not assume a particular task, agent architecture, or objective definition.Source: Problem Formulation · p. 3

Multi-Objective Agent Evolution

  • MOAE maintains an empirical non-dominated archive and selects objective-specialized parents, using a retention tolerance to limit degradation in a specified primary objective.When no primary objective is specified, the method directly uses the archive for parent selection.Source: Multi-Objective Agent Evolution · pp. 3–4
  • Evaluator diagnostics guide a frozen mutation model to propose compact policies, which are validated and evaluated through fresh complete rollouts.The execution agent receives the validated policy rather than the parent trajectory or evaluator annotations; objective values are determined by executing and evaluating the resulting policy.Source: Multi-Objective Agent Evolution · p. 4
  • At deployment, MOAE selects from candidates satisfying specified preservation constraints according to a preference order, with the initial candidate retained as a fallback.The archive can preserve different trade-offs without fixing the final deployment preference during search.Source: Multi-Objective Agent Evolution · p. 4

Experiments

Under matched rollout budgets, MOAE improves task performance, trajectory quality, and safety across TravelPlanner models, with transfer to AgentDojo. Search and ablation analyses examine candidate-pool quality, budget trade-offs, and the contribution of each component.

Experimental Setup

  • Matched-budget comparisons use frozen agents and shared scaffolds, tools, and evaluators; objectives are task constraint satisfaction, trajectory quality, and continuous safety risk, with other metrics reported as audits.Source: Experimental Setup · pp. 4–5

Results

  • About 79% of eventual one-to-25-rollout Task Score gain arrives at seven rollouts, using 28% of the maximum budget, but performance continues improving afterward.Source: Figure 2 · p. 5, Results · p. 5
  • Across three models, Full MOAE improves task performance, trajectory quality, and safety risk over Base Agent; versus Weighted-Sum, it raises task and trajectory scores with fewer tokens.Source: Results · p. 5, Table 1 · p. 6
  • On AgentDojo, MOAE improves utility and trajectory quality over Base Agent and Best-of-7 on Gemma and Qwen3; safety gains appear when vulnerabilities are exposed.Source: Results · pp. 5–6, Table 2 · p. 6
  • Across three seeds, MOAE averages 0.879 task score, 0.991 trajectory quality, and 0.174 safety risk; trajectory quality beats MOCHA-Select by 0.034, while task and safety intervals generally include zero.Source: Results · pp. 6–7
  • 0.52 normalized hypervolume gain beats 0.43 by 20.9%; archive admission rises from 33.9% to 35.6% and joint improvement from 9.4% to 13.9%, although some confidence intervals overlap.Source: Results · p. 6, Figure 3 · p. 7
  • Removing any component lowers joint improvement; mutation removal has the broadest effects, archive removal weakens trajectory and risk gains, and diagnostics particularly affect task completion and safety reduction.Source: Table 3 · p. 7, Results · p. 7

Conclusion

MOAE uses Pareto-preserving search to improve multiple agent properties without fixing a scalar score during search. Results across TravelPlanner and AgentDojo support its promise, while its outcomes remain bounded by evaluators and candidate budget.

Conclusion

  • Across three execution models on TravelPlanner, MOAE improves task performance, trajectory quality, and safety risk; on AgentDojo it improves utility and trajectory quality while eliminating observed attack success.The same candidate pool retains task-, trajectory-, and safety-specialized operating points, with deployment preferences applied afterward.Source: Conclusion · p. 7
  • MOAE preserves task-specialized, trajectory-specialized, safety-specialized, and balanced candidates so deployment constraints, rather than a fixed search-time scalarization, determine the final choice.Improvements in normalized hypervolume, archive admission, and joint-improvement rate support this mechanism, although other methods remain competitive for some models and objectives.Source: Conclusion · p. 7
  • MOAE is an online search bounded by its evaluators and candidate budget; its archive is empirical rather than a global Pareto-front approximation, and search adds inference overhead.The paper identifies adaptive stopping, candidate reuse, and stronger mutation operators as future directions for improving sample efficiency.Source: Conclusion · p. 7

Appendix

The appendix collects experimental and implementation materials, with a stated TravelPlanner validation protocol and fixed comparison components.

Appendix

  • The appendix includes the experimental protocol, evaluator definitions, implementation details, complete results, search analyses, prompts, and qualitative examples.Source: Appendix · p. 9
  • Unless stated otherwise, TravelPlanner results use the validation set and each search method receives the same seven-rollout budget.Source: Appendix · p. 9
  • Within each comparison, the language model, agent scaffold, tools, and evaluators remain fixed.Source: Appendix · p. 9

Experimental Protocol and Reproducibility

The appendix describes matched-budget evaluations across two tool-use benchmarks, with fixed agent and evaluator components. It details comparator methods, objective evaluation, MOAE search and deployment, and protocol checks.

Experimental Protocol and Reproducibility

  • TravelPlanner uses 180 official validation requests, while AgentDojo uses clean and attacked Tool Knowledge cases and reports utility, attack-success, and trajectory-quality metrics.TravelPlanner comparisons share the query, tool environment, base policy, and evaluator; AgentDojo case counts and attack configurations vary by experiment.Source: Benchmarks and Data Splits · p. 9
  • The evaluated comparators include fixed weighted-sum selection, per-query trace-based GEPA-Online under a seven-rollout budget, preference-conditioned MOCHA-Select, and seven independent stochastic executions of the original policy (Best-of-7).Source: Implementation of compared methods · p. 9
  • MOAE runs two generations with one task-, trajectory-, and safety-directed offspring each, updates an empirical nondominated archive, and applies constraint-aware deployment selection after search.The common deployment rule requires task performance no lower and safety risk no higher than the Base Agent, then prioritizes trajectory quality, safety, and task performance.Source: Implementation of compared methods · p. 10, MOAE Search and Deployment… · p. 12, Statistical Protocol and Integrity… · p. 12
  • All search methods use seven complete environment-interacting rollouts per query, versus one for the Base Agent; policy-generation calls add tokens and runtime but not rollouts.The comparison controls complete agent execution while retaining computational differences among search mechanisms.Source: Implementation of compared methods · p. 10
  • The shared evaluator maps complete rollouts to direction-aligned objectives, including task performance, trajectory quality, and safety; AgentDojo attack success is an independent audit metric.Trajectory quality covers valid, grounded, disciplined interaction, including tool execution, information coverage, evidence support, and execution discipline.Source: Objective and Evaluator Design · pp. 10–11, Table 5 · p. 11
  • Equal-weight scalarized search has the strongest normalized hypervolume gain and joint-improvement rate among four tested weight profiles, but changing weights changes the selected point and explored region.The study reports paired-query bootstrap 95% confidence intervals using 10,000 resamples and checks records and candidate counts against the configured budget.Source: Weighted-Sum Baseline and Weight… · p. 12, Statistical Protocol and Integrity… · p. 12

Prompts and Policy Interfaces

MOAE evolves a compact execution policy rather than model parameters or agent architecture; its algorithmic summary covers archive construction, objective-specific mutation, and deployment selection.

Prompts and Policy Interfaces

  • Search prompts expose the parent policy, objective values, and concise evaluator diagnostics, but not hidden benchmark labels or reference answers.Source: Prompts and Policy Interfaces · p. 12
  • Algorithm 1 summarizes per-query archive construction, objective-specific mutation, and deployment selection.Source: Algorithmic Summary · p. 12

Complete Results and Generalization

Across TravelPlanner models, Full MOAE improves on each corresponding Base Agent, while AgentDojo results show task-utility and trajectory-quality gains with zero observed ASR in settings where base attacks succeeded. Robustness checks and search analyses further characterize the results and trade-offs.

Deployment Trade-offs

  • Safety-oriented deployment lowers risk most aggressively but gives up task performance, whereas task-oriented deployment accepts more risk; the balanced rule is an explicit preference, not a universal optimum.The rule returns the initial candidate for 79 of 180 queries and an offspring for 101; selected offspring include 50 task-directed, 24 trajectory-directed, and 27 safety-directed candidates.Source: Cross-Model TravelPlanner Results · pp. 12–13, Archive Dynamics and Parent Diversity · p. 14

AgentDojo Results

  • Gemma Tool Knowledge utility improves by 7.81 percentage points and trajectory quality by 0.2606; on Qwen3 official attacks, utility rises by 12.50 percentage points and trajectory quality by 0.0420.For the Gemma direct-injection setting, the corresponding changes are 3.23 percentage points and 0.1740; Tool Knowledge safety is saturated at zero ASR, while selected Full MOAE trajectories have zero observed ASR where Base Agent attack success is nonzero.Source: AgentDojo Results · p. 13

Cross-Model TravelPlanner Results

  • Task performance rises by 0.092–0.096, trajectory quality by 0.012–0.046, and safety risk falls by 0.096–0.133 across three TravelPlanner execution models.Final Pass Rate also improves for every model, with the largest increase on Gemma; these comparisons are against corresponding base executions, not every matched-budget baseline or operating point.Source: Cross-Model TravelPlanner Results · p. 12, Table 8 · p. 13

Stability and Robustness

  • Full MOAE has the highest mean task score, trajectory quality, and strict trajectory validity across three methods and three seeds, while MOCHA-Select has the lowest mean safety risk.On the expanded 200-query subset, Full MOAE also has the strongest task, trajectory, and safety results among the four compared methods; evaluator and trajectory-weight checks preserve most rankings and selections.Source: Stability across Seeds · pp. 13–14, Additional Generalization and… · p. 14, Table 10 · p. 15

Search Behavior

  • The archive grows from 1.00 candidates after initialization to 2.01 after generation one and 2.52 after generation two; queries use 1.67 distinct parents on average.A total of 64.44% of queries select at least two archive members as parents. The reported search metrics include normalized hypervolume gain, Pareto-set size, archive admission, and strict joint improvement; the latter can be conservative when an initial objective is saturated.Source: Archive Dynamics and Parent Diversity · p. 14, Search Effectiveness Metrics · pp. 14–15

Component Ablations

  • Removing directed mutation causes the largest overall degradation, while removing diagnostics weakens constraint satisfaction and safety repair and removing the archive reduces strict trajectory validity and alternative deployment choices.The components thus have distinct roles: targeted proposals, actionable failure diagnosis, and preservation of alternatives that one scalar incumbent cannot represent.Source: Search Effectiveness Metrics · p. 15

Qualitative Evolution Case Study

The case study traces how MOAE retains candidates with different strengths, then uses a trajectory-specialized parent and evaluator feedback to repair a remaining budget failure. The resulting child satisfies task constraints and is selected for deployment.

Initial Rollout

  • The initial Columbus-to-Newark rollout omits return transportation, makes two invalid actions, and follows instruction-like metadata from an untrusted observation despite satisfying many content constraints.The request specifies a three-day trip for two adults with children under ten, entire-room accommodation, no self-driving, and a $1,200 budget.Source: Qualitative Evolution Case Study · p. 15

First Generation

  • First-generation children preserve different strengths: task-directed c1 has the largest immediate task gain, while trajectory-directed c2 achieves the strongest trajectory quality.The other candidates provide alternative task–trajectory–safety trade-offs, so MOAE retains multiple candidates rather than a single scalarized incumbent.Source: Qualitative Evolution Case Study · p. 15

Second Generation

  • MOAE selects c2 as the trajectory-specialized parent under the task-retention guard; its diagnostics identify the remaining budget constraint.The mutation preserves valid, evidence-grounded tool use while adding total-cost aggregation and enforcement of the $1,200 limit.Source: Qualitative Evolution Case Study · p. 16, Figure 6 · p. 16

Deployment

  • Child c4 satisfies all task constraints, further improves trajectory quality, preserves reduced safety risk, and is selected by the constraint-aware deployment rule.The example links archive preservation, objective-specialized parent selection, and diagnostic-guided mutation: c4 repairs a specific weakness rather than restarting from the original policy.Source: Qualitative Evolution Case Study · p. 16

Token and Runtime Analysis

MOAE separates the cost of searching over complete candidate rollouts from the execution cost of the selected policy. Most additional cost comes from evaluating candidates, not compact mutation calls.

Token Accounting

  • Search tokens cover candidate generation, execution, evaluation, and mutation, while deployment tokens count only the selected candidate’s execution.For local models, six mutation calls use 12.2K tokens on Gemma and 12.4K on Qwen3; selected-policy execution cost remains close to the Base Agent.Source: Token and Runtime Analysis · p. 16

Cost Profile

  • Most search cost comes from complete candidate rollouts rather than mutation, and DeepSeek API logs do not expose the same execution–mutation decomposition or directly comparable local runtime.The comparison distinguishes matched environment-interaction budgets from identical total token use or wall-clock cost.Source: Token and Runtime Analysis · p. 16

Closest-Work Comparison

MOAE differs from related optimizers by applying limited-budget search independently per query and separating rollout-level candidate retention from deployment choice. The reported scope is bounded by its small empirical archives, objective definitions, evaluators, benchmarks, and online cost.

Closest-Work Comparison

  • Unlike methods optimizing reusable artifacts over task collections, MOAE searches per query under seven rollouts, preserving rollout-level trade-offs before constraint-aware deployment selection.This distinguishes its setting, not a claim that it is the first method to use evolution or nondominated selection.Source: Closest-Work Comparison · p. 16, Table 15 · p. 17

Limitations, Failure Modes, and Reporting

  • Each archive contains at most seven evaluated candidates and is an empirical nondominated set, not an approximation to a global Pareto front or evidence of global optimality.Archive size alone is not a quality measure, and hypervolume comparisons depend on objective normalization and the reference point.Source: Limitations, Failure Modes, and… · p. 16
  • MOAE can optimize only evaluator-represented properties, so missed failures or misspecified metrics can yield measured gains without intended improvement; robustness checks cannot exclude all metric overfitting.Held-out evaluator and alternative-weight analyses show that most ordering and improvements transfer under tested changes.Source: Limitations, Failure Modes, and… · p. 17
  • The safety results cover predefined probes, tested attack families, tool interfaces, and monitored paths; zero observed attack success is not a universal robustness guarantee.Safety-oriented candidates can also sacrifice task utility.Source: Limitations, Failure Modes, and… · p. 17
  • Deployment safeguards prevent measured regression against the observed initial rollout, but stochastic single executions do not guarantee improved expected performance or reproducible behavior on a fresh rollout.The initial candidate remains feasible, so it is returned when no offspring satisfies both deployment constraints.Source: Limitations, Failure Modes, and… · pp. 17–18
  • MOAE uses seven complete rollouts and six policy-generation calls per query, making it training-free but not cost-free; matched rollout budgets do not mean equal token use or runtime.The seven-rollout setting is not a convergence guarantee and may be unsuitable for latency-sensitive or costly, state-changing environments.Source: Limitations, Failure Modes, and… · p. 18
  • The matched-budget baseline adaptations improve internal comparability but do not rank the original methods in their native settings; the artifact records search details while excluding credentials and sensitive attack payloads.The adaptations intentionally align artifact scope, development-set size, and rollout harness; potentially harmful injection payloads are not reproduced verbatim.Source: Limitations, Failure Modes, and… · p. 18
  • Evidence spans TravelPlanner and AgentDojo, three execution models, and compact textual policies, but does not establish generality across architectures or untested settings such as persistent memory or embodied interaction.Three seeds do not characterize every source of generation variance, and confidence intervals over evaluated queries are not guarantees for another task distribution.Source: Limitations, Failure Modes, and… · p. 18

Related papers

Loading 2609.05992v1…