Maestro: Joint Graph & Config Optimization for Reliable AI Agents

Challenges of reliable agents

• Agents can fail through instruction drift, corner-case brittleness, state loss, fragile pipelines, weak error recovery, and context or memory constraints.These reliability problems motivate optimizing beyond prompts alone.Source: §1 · p. 2

Challenges and prior work

• Reliable-agent optimization must jointly address structure and configuration because the search is high-dimensional, mixed-type, dependent, and often multi-criteria.Prior approaches often hold the graph fixed, restrict topology, or rely on scalar feedback, leaving parts of the design space and qualitative signals underused.Source: §1 · p. 2

Maestro

• Maestro is framework-agnostic and searches typed agent graphs with non-sequential routing, persistent state, context gating, and per-node model and tool choices.Its graph can include branching, retries, explicit state read/write policies, and tunable hyperparameters.Source: §1 · pp. 2–3
• Reflective feedback from traces is distilled into targeted graph and configuration edits for failures such as instruction drift, looping, state loss, and brittle control flow.The feedback includes evaluator rubrics and free-form critiques, in addition to aggregate scores.Source: §1 · p. 3

Results

• 70.33% on HotpotQA with 240 rollouts and 56.12% on IFBench with 700 rollouts for Maestro-optimized prompts; graph-plus-prompt optimization reaches 72.33% on HotpotQA and 59.18% on IFBench.The prompt-only results exceed GEPA’s 69.00% on HotpotQA after 6,000+ rollouts and its 55.95% peak on IFBench after 3,000+ rollouts; graph-plus-prompt results exceed leading baselines by more than 3%.Source: Figure 1 · p. 1, §1 · p. 3
• Holistic optimization improves the interviewer and AI assistant by an average of 65.7%, versus 41.9% for configuration-only optimization.The reported holistic gains are 90% and 41.3%, respectively; qualitative changes include revised control logic, explicit memory nodes, context gating, and validator insertion.Source: §1 · p. 3

AGENTIC COMPUTATION GRAPH

• An agent is a directed graph with optional input and output node sets, and each node has its own input and output sets.Source: AGENTIC COMPUTATION GRAPH · p. 3
• Node inputs are assembled using a merge operator with hyperparameters; a node with one parent uses the identity operator.Source: AGENTIC COMPUTATION GRAPH · pp. 3–4
• Each agentic node is modeled as a stochastic function with a configuration that can include its model, prompt, tools, decoding, and control settings.Source: AGENTIC COMPUTATION GRAPH · p. 4
• Cycles can be handled by unrolling execution over time and reading out at the final step, or by using a well-defined fixed-point operator.Source: AGENTIC COMPUTATION GRAPH · p. 4
• Conditional edge activations support routing or gating by letting the merge operator ignore inputs from inactive edges.Source: AGENTIC COMPUTATION GRAPH · p. 4

2.1 TASK, EVALUATION, AND COSTS

• Expected task utility evaluates the graph’s outputs against an evaluation metric, with expectation taken over execution randomness.Source: §2.1 · p. 4
• The formulation accounts for execution resource costs, such as tokens, latency, or tool fees, and can regularize graph complexity.Source: §2.1 · p. 4

2.2 JOINT OPTIMIZATION OVER GRAPH AND CONFIGURATIONS

• Joint optimization chooses both graph structure and node, adapter, and merge configurations to maximize expected utility under structure and rollout budgets.The search includes discrete and continuous decisions, and the rollout budget represents limited experimentation or feedback.Source: §2.2 · p. 4

• MIPROv2 uses sequential surrogate-driven candidate selection over configurations, with graph topology unchanged throughout.Its acquisition function balances exploration and exploitation using observed utility and cost.Source: §3 · p. 5
• GEPA uses reflective, multi-objective evolutionary search over configurations, selecting a diverse Pareto front while holding topology constant.Source: §3 · p. 5
• GRPO fine-tunes model parameters within nodes using group-relative advantages and a clipped objective, without changing the agent graph.Source: §3 · p. 5
• All three described optimizers tune configurations under constraints but do not search over graph structure.Source: §3 · p. 5

• Maestro is presented as framework-agnostic and jointly optimizes an agent’s structural and operational dimensions.It provides utilities for registering configurations and tracking agent activity across implementations.Source: §4 · pp. 5–6
• Maestro alternates between configuration updates with the graph fixed and graph updates with configurations fixed, using numeric and reflective feedback to guide both.Source: §4 · p. 5
• Graph updates explore a local neighborhood of structural edits within an edit-distance trust region and use warm-started configurations for candidate evaluation.The method uses a budget-aware objective estimate and splits budget across iterations.Source: §4 · p. 5
• Figure 3 compares HotpotQA agent graphs before and after Maestro optimization, with blue highlighting optimizer-suggested nodes and edges.Source: Figure 3 · p. 6
• Reflective feedback from execution traces and evaluation rationales guides proposals in both optimization blocks without requiring differentiability.Source: §4 · p. 6
• Estimated objectives improve monotonically under fixed budgets and constraints, but global optimality is not guaranteed in the mixed discrete-continuous, nonconvex setting.Technical details of the general formulation remain proprietary.Source: §4 · pp. 5–6

5.1.1 SETUP

• The HotpotQA setup uses GEPA’s data splits, initial agent, and evaluator; prompt-only optimization fixes the model and tunes four module prompts.The agent is a two-hop retrieval pipeline, evaluated by average exact-answer match; Maestro also receives textual feedback about relevant documents remaining to retrieve.Source: §5.1.1 · pp. 6–7

5.1.2 RESULTS

• 72.33% on HotpotQA after 2,220 rollouts followed graph optimization, while the combined agent reached 72.00% after 420 rollouts.The proposed graph adds an entity-extraction step to give the second-hop query writer concrete handles.Source: §5.1.2 · p. 7

5.2.1 SETUP

• IFBench tests precise instruction-following generalization across diverse, verifiable constraints using GEPA’s evaluation protocol and the same initial agent and data splits.The two-stage agent drafts a response and rewrites it to satisfy user constraints; evaluation averages the fraction of constraints followed and supplies descriptions of failures.Source: §5.2.1 · pp. 7–8

5.2.2 RESULTS

• 59.18% on IFBench after 900 rollouts surpasses GEPA/GEPA+Merge peak performance reported after more than 3000 rollouts, with a validation-and-rewrite module added to the graph.The added module checks constraint violations and triggers another rewrite with ensure_correct_response.Source: §5.2.2 · p. 8, Figure 6 · p. 8

5.3.1 SETUP

• The interviewer application simulates multi-round financial interviews covering five predefined branches, using 50 training personas and 10 held-out test personas.Five trajectories per test persona yield 50 test cases; the baseline is a single agent whose model and system prompt are tunable.Source: §5.3.1 · p. 9

5.3.2 RESULTS

• 92% of interviewer test cases were complete with graph and configuration optimization, compared with 66% with configuration optimization and 2% initially.The optimized graph tracks completed branches in external state variable branches_done.Source: §5.3.2 · p. 10, Figure 8 · p. 10

5.4.1 SETUP

• The financial RAG agent is evaluated on factual, quantitative, out-of-distribution, and adversarial queries within a scope limited to Apple, Alphabet, and Nvidia.Its initial tools search company filings and retrieve historical stock prices; Maestro can tune the model, retrieval-chunk count, and system prompt.Source: §5.4.1 · pp. 10–11

5.4.2 RESULTS

• Both RAG optimization modes substantially improved on the initial design, and the joint mode added computation tools for mean, standard deviation, and percentage growth.The initial agent left these computations to the LLM, which the paper describes as slower, more expensive, and more error-prone for large arrays.Source: §5.4.2 · p. 12, Figure 10 · p. 12, Figure 9 · p. 12

6 CONCLUSION

• Maestro alternates configuration and graph optimization, using trust-region edits, warm starts, and budgeted evaluation within a unified formulation.The formulation treats agents as typed stochastic computation graphs and couples task utility with cost, structure, and rollout budgets.Source: §6 · pp. 12–13
• Across IFBench and HotpotQA, Maestro delivered consistent gains under matched budgets and substantially improved reliability over strong configuration-only baselines in two applications.The applications were an interviewer agent and an AI assistant.Source: §6 · p. 13
• Reflective feedback from execution traces is distilled into targeted edits for failures such as missing verification, brittle control flow, and inadequate state handling.The conclusion says configuration-only methods cannot reliably fix these failure modes.Source: §6 · p. 13
• Structure determines which computations are possible, while configuration determines how well they are realized; budgeted search makes trade-offs among accuracy, latency, and cost explicit.The conclusion frames holistic graph-and-configuration optimization as a necessary ingredient for reliable, efficient agents.Source: §6 · p. 13
• Warm starts and reflective guidance help tailor agents to use-case metrics and budgets, with the stated aim of improving accuracy, controllability, and cost awareness.The conclusion contrasts this approach with monolithic agents that overfit to happy paths, lack recovery instrumentation, or use unnecessary computation.Source: §6 · p. 13

A.1.1 INITIAL CONFIGURATION

• The initial second-hop query generator receives question and summary_1 and produces a query.Its prompt heading identifies the module as create_query_hop2.Source: §A.1.1 · p. 15
• The specified process takes three fields—question, summary_1, and summary_2—as inputs and produces one field, answer, as its output.Source: §A.1.1 · p. 15
• The initial summarizers map question and passages to summary, while the second summarizer additionally receives context.The first interface uses question and passages; the second uses question, context, and passages.Source: §A.1.1 · p. 15

A.1.2 OPTIMIZED CONFIGURATION

• The optimized final-answer prompt instructs the module to answer using only summary_1 and summary_2 and return only the answer text.The output format excludes explanations, prefixes, punctuation, and additional formatting.Source: §A.1.2 · p. 16
• The optimized first-hop summarizer selects passages relevant to the question and copies each selected fact verbatim in an EntityName | fact format.It is instructed to omit irrelevant passages and avoid adding, inferring, or paraphrasing information.Source: §A.1.2 · p. 16
• The optimized second-hop summarizer integrates context and new passages into an entity-organized summary of relevant facts.It prioritizes passage text when it corrects or expands a context fact and prohibits unsupported inference.Source: §A.1.2 · p. 17

A.1.3 OPTIMIZED GRAPH

• A new extract_entities module extracts query-driving terms from summary_1, and its output is added to the second-hop query generator's inputs.The updated call passes question, summary_1, and entities to create_query_hop2.Source: §A.1.3 · p. 18
• The extraction prompt selects exact bracketed subject entities from summary_1 and adds question-mentioned answer choices not already included.It excludes other text and preserves the terms' order of appearance.Source: §A.1.3 · p. 19
• The updated query prompt checks whether summary_1 contains the question's names, key concepts, and required relation, then searches for the most important missing term.The resulting query starts with that term and appends up to two disambiguating words from the question or summary.Source: §A.1.3 · p. 19
• The optimized first-hop summarizer requires one traceable fact per bullet, prefixed by its subject in square brackets.It prohibits combining facts and directs the module to include question-relevant terms.Source: §A.1.3 · p. 20
• The optimized second-hop summarizer integrates context and passages into 2–4 fact bullets, while the final-answer module returns only a minimal answer.The second-hop prompt says to prioritize passages when they conflict with context; the final-answer prompt specifies yes/no or a minimal entity, term, or phrase.Source: §A.1.3 · pp. 19–21

A.2.1 INITIAL CONFIGURATION

• The initial prompts simply request step-by-step reasoning and place reasoning and final answers in tagged blocks.The generate_response and ensure_correct_response prompts both use this basic format.Source: §A.2.1 · p. 21

A.2.2 OPTIMIZED CONFIGURATION

• The optimized generate_response prompt extracts explicit requirements, plans and validates compliance, and returns only a formatted answer or a clarification for irreconcilable constraints.It also specifies fast paths for simple calculations or fixed-template requests and best-effort fallbacks for minor contradictions.Source: §A.2.2 · pp. 21–22
• The optimized ensure_correct_response prompt classifies explicit constraints and defines precise counting, parsing, and formatting checks before producing a compliant answer.It calls for revalidation after minimal fixes and specifies a clarification response when a requirement remains impossible or contradictory.Source: §A.2.2 · p. 22
• The optimized graph adds a constraint validator after the second-pass rewrite and performs one further rewrite when violations are found.The validator compares the candidate answer with the original instructions; the corrective rewrite receives its violation list.Source: §A.2.3 · pp. 22–23
• The optimized configuration checks extracted constraints, reports failures, and either reproduces the original response or minimally corrects it inside the required output blocks.It also instructs the assistant to place no text outside the <think> and <output> sections.Source: §A.2.3 · p. 26

A.3.1 INITIAL CONFIGURATION

• The initial interviewer presents five financial-planning branches, starts with the user’s priority, covers all branches, and ends with a summary of collected information.The branches concern budgeting, retirement, investment, debt, and major life events.Source: §A.3.1 · pp. 26, 27, 29

A.3.2 OPTIMIZED CONFIGURATION

• The optimized configuration defines a stateful financial-planning assistant that tracks visited branches and answers and specifies question sequences for budgeting and retirement.The supplied sequence also begins the investment branch with a question about whether the user currently has investments.Source: §A.3.2 · pp. 29–30
• The optimized interviewer follows ordered branches, then asks about a financial habit, an area to improve, and whether the user wants a custom plan before summarizing.Its flow prohibits re-asking the initial question, skipping or reordering sub-questions, and producing a summary before Q32.Source: §A.3.2 · p. 30

A.3.3 OPTIMIZED GRAPH

• The optimized graph tracks completed branches in external state, supplies completed and remaining branches to the model, and updates state from branch-completion markers.The state is prepended to model input when branches are complete and the agent has not yet produced a summary.Source: §A.3.3 · p. 31

A.4.1 INITIAL CONFIGURATION

• The initial financial agent uses gpt-4o-mini-2024-07-18, retrieves one chunk, and is prompted to answer questions about Apple, Google (or Alphabet), or Nvidia financials.Source: §A.4.1 · p. 31

A.4.2 OPTIMIZED CONFIGURATION

• The optimized financial assistant uses gpt-4.1-mini-2025-04-14 for public 2024 financial data about Apple, Alphabet (Google), or Nvidia, with retrieval instructions for single-year items and multi-year aggregates.For multi-year aggregates, it first retrieves the consolidated financial-statement notes table for years ending December 31, YYYY–2024, or fetches each year's note individually if unavailable.Source: §A.4.2 · p. 31
• The optimized prompt requires numeric_compute for calculations, preserves exact retrieved figures, specifies numeric formatting, and refuses requests outside its data scope or for non-public or personal information.If an exact figure is unavailable, it requires “Data not available”; out-of-scope requests receive a specified confidentiality refusal.Source: §A.4.2 · pp. 31–32

A.4.3 OPTIMIZED GRAPH Suggested numeric compute tool:

• The suggested numeric_compute tool supports average and percentage-growth operations, rounds results to two decimals, and raises an error for unknown operations.Source: §A.4.3 · p. 32