cs.MAOct 10, 2026

Optimize Once, Execute Fast: Latency-Aware Multi-Agent Workflow Learning for Recurrent Queries

Authors: Enpei Zhang, Feiyu Qu, Zheng Huang, Dawei Zhou, Elynn Chen, Yujun Yan

Organizations: Dartmouth College · Virginia Tech · New York University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Large Language Model-based Multi-Agent Systems (LLM-based MAS) have shown remarkable success in solving complex tasks by coordinating specialized agents through multi-step workflows. To overcome the high cost and specificity of manually designed workflows, recent research has shifted toward learning them automatically. However, a key limitation remains: while agent calls introduce significant latency due to model inference time and service congestion, most automated methods optimize solely for downstream performance, ignoring execution time (makespan). This issue is amplified when workflows are reused across recurring queries, making latency accumulate over time. This limits deployment in recurrent applications such as AI customer support and AI cloud troubleshooting, where users expect fast responses. To bridge this gap, we introduce a new problem, termed latency-aware workflow generation, where the objective is to minimize workflow makespan while aiming to retain downstream performance. We propose LAWA (Latency-Aware Workflow optimizAtion), a novel framework that reduces makespan via theoretically grounded graph edits targeting critical-path bottlenecks. By unifying a graph generator with this graph-editing procedure, LAWA supports both de novo workflow generation and refinement of existing ones. Empirical results across seven benchmarks demonstrate that LAWA significantly reduces makespan while achieving competitive task performance, supporting efficient reuse of multi-agent workflows for recurrent queries.

Figures & tables

Figure 1: Overview of LAWA. Three main components of LAWA: (left) graph editing operations including node permutation, parallel rewiring, and node removal; (middle) a structural optimization engine that initializes a workflow, generates and ranks candidate graphs by makespan, and iteratively selects valid modifications; and (right) the training pipelines for the graph generator and graph evaluator based on empirical downstream task performance.
MethodMBPPHumanEvalAQuAGSM8KMATH500SVAMPMMLUAvg. Rank
Rand. Graph16.92_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.53}}19.80_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.48}}24.16_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.42}}17.13_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.24}}26.33_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.41}}17.24_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.12}}18.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.43}}8.868.86
Rand. Chain22.67_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.52}}22.26_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.94}}31.34_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.65}}27.90_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.08}}36.86_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.29}}23.54_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.25}}24.06_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.22}}10.5710.57
3-Round Disc.17.52_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.84}}15.08_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.71}}17.04_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.61}}15.06_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.10}}21.04_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.94}}13.60_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.76}}13.93_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.13}}7.297.29
DyLAN11.46_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.34}}\hbox{\pagecolor{blue!15}{{\color[rgb]{0,0,0}11.29}}}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.08}}13.65_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.10}}\hbox{\pagecolor{blue!15}{{\color[rgb]{0,0,0}8.09}}}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.19}}16.63_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.23}}9.38_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.61}}9.11_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.26}}3.143.14
G-Designer25.27_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.75}}24.01_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.28}}15.56_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.26}}9.74_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.55}}21.34_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 9.46}}23.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4.08}}25.32_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.43}}9.439.43
AgentDropout13.92_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5.56}}14.24_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.73}}13.85_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.42}}9.57_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.95}}21.54_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 7.58}}16.72_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.80}}17.31_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4.21}}6.146.14
Table 1: Real wall-clock makespan (Seconds ↓\downarrow ) per query on 7 benchmarks. All methods are evaluated using agents powered by Qwen3-30B-A3B-Instruct-2507 with different roles. Each method is tested three times and results are mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} . The first and second best entries in each column are highlighted. LAWA achieves the lowest makespan on six of seven benchmarks and the best average rank.
MethodMBPPHumanEvalAQuAGSM8KMATH500SVAMPMMLUAvg. Rank
Rand. Graph63.94_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.49}}92.07_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.99}}80.58_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.67}}93.23_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.20}}66.53_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.41}}93.67_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.62}}65.33_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4.94}}7.367.36
Rand. Chain64.07_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.73}}91.67_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.76}}80.31_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.64}}93.91_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.15}}66.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.57}}93.30_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.37}}64.11_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5.60}}8.008.00
3-Round Disc.64.33_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.12}}92.89_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.76}}72.57_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.98}}94.77_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.21}}63.80_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.28}}\hbox{\pagecolor{orange!20}{{\color[rgb]{0,0,0}94.27}}}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.29}}65.66_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.29}}6.646.64
DyLAN64.72_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.02}}\hbox{\pagecolor{blue!15}{{\color[rgb]{0,0,0}93.29}}}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.32}}80.71_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.96}}95.80_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.23}}65.87_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.41}}93.67_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.24}}{68.03}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.09}}4.794.79
G-Designer63.81_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.10}}89.84_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.76}}76.77_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.79}}94.16_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.33}}66.13_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.09}}{94.20}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.29}}67.71_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.17}}7.717.71
AgentDropout{64.59}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.91}}91.06_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.24}}{80.84}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.30}}93.58_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.83}}66.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.09}}93.27_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.65}}65.97_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.15}}7.077.07
Table 2: Comparison of task performance (Accuracy ↑\uparrow ) on 7 Benchmarks. All methods are evaluated using agents powered by Qwen3-30B-A3B-Instruct-2507 with different roles. Each method is tested three times and results are mean ±std{}_{\pm\text{std}} . The first and second best entries in each column are bolded with colors. LAWA maintains comparable or superior accuracy to the baselines, achieving the best average rank.
Figure 2: Visualization of Workflow Topology and Execution Gantt Chart. We visualize the workflow of three representative methods on one MBPP task. The top row shows the workflow graphs where red arrows denote the critical path, with the wall-clock latency labeled on each node. The bottom row shows the corresponding Gantt charts, with red-outlined blocks highlighting critical path tasks. LAWA generates the workflow with the shortest critical path to achieve maximal parallel execution and the shortest makespan.
DatasetRandom GraphRandom ChainAgentPruneAgentDropout
Acc (%)Makespan (s)Acc (%)Makespan (s)Acc (%)Makespan (s)Acc (%)Makespan (s)
HumanEval\textbf{+}1.63_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.53}}\textbf{-}4.40_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.97}}\textbf{+}0.20_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.57}}\textbf{-}7.61_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.04}}\textbf{+}1.42_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.88}}\textbf{-}2.79_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.46}}\textbf{+}0.81_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.35}}\textbf{-}2.19_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.56}}
MBPP\textbf{+}0.26_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.49}}\textbf{-}5.39_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.49}}\textbf{+}0.39_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.84}}\textbf{-}6.86_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.06}}\textbf{+}0.91_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.20}}\textbf{-}2.41_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.72}}\textbf{+}0.13_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.63}}\textbf{-}2.75_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.73}}
AQuA\textbf{+}0.52_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.74}}\textbf{-}4.92_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.59}}\textbf{+}0.52_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.19}}\textbf{-}8.05_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.11}}\textbf{+}1.84_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.17}}\textbf{-}3.65_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.06}}\textbf{+}0.79_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.96}}\textbf{-}3.21_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.12}}
GSM8K\textbf{+}0.25_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.25}}\textbf{-}6.16_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.33}}\textbf{+}0.08_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.07}}\textbf{-}8.17_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.01}}\textbf{+}0.08_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.75}}\textbf{-}3.06_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.43}}\textbf{+}1.26_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.26}}\textbf{-}2.78_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.24}}
MATH500\textbf{+}0.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.57}}\textbf{-}6.63_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.57}}\textbf{+}0.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.57}}\textbf{-}8.66_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.16}}\textbf{+}0.07_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.90}}\textbf{-}3.35_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.42}}\textbf{+}0.13_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.52}}\textbf{-}3.71_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.13}}
Table 3: LAWA as a Plug-in Module. We apply LAWA to the workflow graphs generated by four baseline methods and report the resulting changes in accuracy and makespan (mean ±std{}_{\pm\text{std}} ) relative to the original baseline performance. LAWA consistently compresses the makespan of these diverse initial workflows with non-negative mean accuracy changes in the reported runs, validating its role as a flexible plug-in module.
Datasetα\alpha =0.00α\alpha =0.10α\alpha =0.20
HumanEval92.89_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.04}}92.48_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.35}}91.67_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.53}}
MBPP66.28_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.37}}66.28_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.59}}65.76_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.67}}
AQuA83.46_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.85}}83.34_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.82}}82.83_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.38}}
MATH50067.00_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.86}}66.73_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.31}}65.87_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.23}}
Table 4: RQ3: Robustness under evaluator perturbations. We flip the evaluator’s keep/reject decision with probability α\alpha , and report the task accuracy (%) of the generated workflows as mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} . Performance remains close to the unperturbed setting for small flip rates ( α≤0.2\alpha\leq 0.2 ).
 AQuASVAMPMMLU
AblationΔ\Delta Acc.Δ\Delta TimeΔ\Delta Acc.Δ\Delta TimeΔ\Delta Acc.Δ\Delta Time
w/o Node Removal−0.65-0.65+1.96+1.96−4.71-4.71+8.30+8.30−3.36-3.36+15.92+15.92
w/o Parallel Rewiring−0.78-0.78+1.64+1.64−4.45-4.45+4.97+4.97−2.25-2.25+18.67+18.67
w/o SFT−2.75-2.75−1.96-1.96−0.68-0.68+2.37+2.37−1.66-1.66+5.51+5.51
w/o DPO−3.41-3.41+7.26+7.26−3.40-3.40−0.36-0.36−6.81-6.81+13.08+13.08
Table 5: RQ4: Component ablations. Changes in accuracy (%) and makespan (s) relative to full LAWA. Removing any component reduces accuracy on all three benchmarks.
Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Example of iterative workflow optimization on MBPP. We visualize the original chain-structured workflow (top-left) and the resulting workflows after 1, 2, and 3 optimization steps (top-right, bottom-left, bottom-right, respectively). For each panel, the upper plot shows the workflow graph, where red arrows denote the critical path, and the lower plot shows the corresponding execution Gantt chart with critical-path agent executions highlighted (both using estimated tkt_{k} ). As LAWA applies successive structural modifications, the workflow topology departs from the initial chain, progressively shortening the critical path and reducing makespan.
mmRuntime Improvement (%)Operation Counts (rewire/remove)
143.6719/64
265.3883/61
367.7491/59
467.8992/59
Appendix
Table 6: Behavior of LAWA under limited executors. Here mm is the number of available executors; runtime improvement is the relative reduction versus the initial workflow; operation counts are total rewiring/node-removal edits aggregated over all generated instances (7 benchmarks ×\times 3 runs).
SettingMATH500HumanEvalAQuA
w/o approximation67.00_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.71}}93.29_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.00}}83.86_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.56}}
w/ approximation67.00_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.86}}92.89_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.04}}83.46_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.85}}
Appendix
Table 7: Accuracy robustness under rewiring-score approximation on three benchmarks. We compare LAWA with and without first-order approximation when filtering rewiring edits. Values are accuracy (%, mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} ) over 3 runs. Results show that the approximation does not introduce a noticeable drop in accuracy.
MethodMBPPHumanEvalAQuAGSM8KMATH500SVAMPMMLU
Rand. Graph22768_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1949}}34403_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4326}}64483_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2350}}40409_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 8685}}57252_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 8018}}40825_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1684}}48050_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 6204}}
Rand. Chain40289_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4229}}49315_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3638}}99064_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 11753}}83317_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 446}}103547_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5895}}71156_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1235}}73758_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 821}}
3-Round Disc.219103_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 7310}}243745_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3320}}595536_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 12769}}500286_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2419}}646475_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 21625}}445061_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 7785}}470002_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1510}}
DyLAN55388_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3921}}72015_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5500}}85396_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 9330}}41915_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 20638}}98495_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3777}}62078_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2553}}81276_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1301}}
G-Designer37128_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2550}}44954_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1157}}88371_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4124}}80719_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3347}}99698_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4556}}70241_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5089}}67340_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2960}}
AgentDropout19870_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 9307}}27288_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 10278}}54616_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5328}}29668_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 7334}}46292_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 7966}}41654_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4011}}46553_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 10920}}
Appendix
Table 8: Total token consumption per query (Tokens ↓\downarrow ) on seven benchmarks. We report total token consumption (input + output) for all methods. Values are mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} over three runs, and the best value in each benchmark is bolded.
BenchmarkTime (s)
MBPP2.2736_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.2287}}
HumanEval1.1563_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.4062}}
AQuA1.6917_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.7676}}
GSM8K2.2471_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.1613}}
MATH5001.7981_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.1430}}
SVAMP2.2039_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.2768}}
Appendix
Table 9: Wall-clock time to generate a single workflow (Seconds ↓\downarrow ).
BenchmarkTrain Time (s)
MBPP44.45
HumanEval21.32
AQuA63.34
GSM8K34.65
MATH50046.47
SVAMP23.32
Appendix
Table 10: Wall-clock time to train the Graph Evaluator (Seconds ↓\downarrow ).
 MBPPMATH500MMLU
MethodAcc.TimeAcc.TimeAcc.Time
DyLAN73.41_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.22}}40.27_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 5.92}}81.20_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.25}}32.01_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 9.53}}80.73_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.80}}33.07_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.03}}
AgentDropout72.24_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.59}}43.66_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.37}}79.27_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.89}}43.34_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.98}}79.82_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.61}}52.66_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 13.15}}
LAWA\textbf{73.80}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.81}}\textbf{14.19}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.21}}\textbf{81.27}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.22}}\textbf{18.43}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.99}}\textbf{81.74}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.77}}\textbf{19.75}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.10}}
Appendix
Table 11: Accuracy (% ↑\uparrow ) and real wall-clock makespan (s ↓\downarrow ) with Kimi-K2.6. Values are mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} over three workflow graphs.
DatasetMethodStep 1Step 2Step 3Step 4Step 5
HumanEvalLAWA (w/ Evaluator)\textbf{+1.68}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.99}}\textbf{+2.21}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.97}}\textbf{+2.29}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.22}}\textbf{+2.44}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.37}}\textbf{+1.75}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.54}}
HumanEvalw/o Evaluator-0.30_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.14}}-0.15_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.82}}-0.07_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.26}}-0.53_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.12}}-2.74_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.72}}
MATH500LAWA (w/ Evaluator)\textbf{+0.95}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.60}}\textbf{+1.65}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.09}}\textbf{+1.25}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.17}}\textbf{+1.65}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.14}}\textbf{+1.35}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.23}}
MATH500w/o Evaluator-0.20_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.63}}-0.35_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.19}}-0.45_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.19}}-0.63_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.34}}-1.72_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.51}}
Appendix
Table 12: Performance change across optimization steps with and without the Graph Evaluator. Values are downstream-performance changes (%, mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} ) relative to the initial workflow, computed over eight different random initial graphs.
Hidden DimGNN Type#LayersTrain Acc (%)Test Acc (%)
256gcn194.68_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.68}}94.79_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.35}}
256gcn294.63_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.49}}95.17_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 4.28}}
256gcn3\textbf{95.05}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.44}}\textbf{95.14}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 2.58}}
256gcn494.93_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.20}}95.77_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.30}}
256gat194.97_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 0.73}}94.47_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.27}}
256gat295.38_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 1.27}}94.00_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm 3.74}}
Appendix
Table 13: GNN architecture ablation on HumanEval for Graph Evaluator. We vary GNN type ( gcn , gat , transformer ), number of layers ({1,2,3,4}), and hidden dimension ({256,512}), while keeping other training settings fixed. Values are train/test accuracy (%, mean {}_{\scriptsize{\color[rgb]{0.3,0.3,0.3}\pm\text{std}}} ) over 3 seeds. Rows where both train and test mean exceed 95 are bolded.
More in this topic

LLM Agent Workflow Optimization

LLM agent workflow optimization studies how to design and run multi-step agents for better task success, reliability, latency, and cost.

See all 262 papers

Explore similar work

CardsList
Jul 15, 2026

Learning Latency-Aware Orchestration for Multi-Agent Systems

Multi-agent systems (MAS) coordinate multiple LLM-powered agents through structured workflows, gaining reasoning power but incurring high inference latency from multi-step execution and repeated model invocations. Existing orchestration methods primarily optimize task performance and inference cost, leaving latency largely unaddressed. In MAS, end-to-end latency is governed by the critical execution path, so reducing total cost alone does not reliably reduce latency. Moreover, optimizing latency while preserving accuracy remains non-trivial: naive latency optimization can misassign operator-level credit and degrade task accuracy. To address this gap, we propose Latency-Aware Multi-agent System (LAMaS), a latency-aware orchestration framework for learning-based multi-agent systems. LAMaS addresses this challenge at two levels: at training time, it learns latency-aware execution graphs through constrained optimization with critical-path-aware credit assignment; at inference time, since a graph committed at training time cannot exploit runtime evidence, it complements graph construction with a lightweight controller that adaptively eliminates redundant future agent interactions as execution unfolds. Experiments on four benchmarks show that LAMaS achieves the best latency among evaluated learning-based MAS baselines, reducing end-to-end latency by over 50% while maintaining competitive or better accuracy. LAMaS is also modular and transfers to other MAS with minimal changes, consistently yielding latency reductions.

Xi Shi, Mengxin Zheng, Qian Lou

University of Central Florida

Multi-Agent LLM SystemsMulti-Agent System OptimizationMulti-Agent Orchestration
AskPDF
Mar 22, 2026

WorkflowGen:an adaptive workflow generation mechanism driven by trajectory experience

Large language model (LLM) agents often suffer from high reasoning overhead, excessive token consumption, unstable execution, and inability to reuse past experiences in complex tasks like business queries, tool use, and workflow orchestration. Traditional methods generate workflows from scratch for every query, leading to high cost, slow response, and poor robustness. We propose WorkflowGen, an adaptive, trajectory experience-driven framework for automatic workflow generation that reduces token usage and improves efficiency and success rate. Early in execution, WorkflowGen captures full trajectories and extracts reusable knowledge at both node and workflow levels, including error fingerprints, optimal tool mappings, parameter schemas, execution paths, and exception-avoidance strategies. It then employs a closed-loop mechanism that performs lightweight generation only on variable nodes via trajectory rewriting, experience updating, and template induction. A three-tier adaptive routing strategy dynamically selects among direct reuse, rewriting-based generation, and full initialization based on semantic similarity to historical queries. Without large annotated datasets, we qualitatively compare WorkflowGen against real-time planning, static single trajectory, and basic in-context learning baselines. Our method reduces token consumption by over 40 percent compared to real-time planning, improves success rate by 20 percent on medium-similarity queries through proactive error avoidance and adaptive fallback, and enhances deployability via modular, traceable experiences and cross-scenario adaptability. WorkflowGen achieves a practical balance of efficiency, robustness, and interpretability, addressing key limitations of existing approaches.

Ruocan Wei, Shufeng Wang, Ziwei Shi

China Telecom Cloud, Beijing, China

Agentic WorkflowsLLM Agent Workflow OptimizationMemory-Augmented Language Model Agents
AskPDF
Jun 9, 2026

FlowBank: Query-Adaptive Agentic Workflows Optimization through Precompute-and-Reuse

Large Language Model (LLM)-based multi-agent systems are increasingly powerful, but current agentic workflow optimization paradigms make an unsatisfying trade-off. Task-level methods spend substantial offline compute yet deploy only a single workflow, leaving complementary candidates unused, while query-level methods synthesize a new workflow per query at substantial inference cost. Our motivating analysis shows these paradigms are more complementary than competing: workflows discovered during offline search often solve different subsets of queries, and many queries handled by expensive query-level generation can already be solved by cheaper precomputed workflows. This suggests a different objective: rather than searching for one universally best workflow or regenerating one per instance, we should build a compact bank of reusable, complementary workflows and select among them adaptively at inference time. Doing so requires solving three coupled problems: generating complementary rather than redundant candidates, compressing them into a small deployable portfolio, and assigning each query to the right workflow under a performance-cost trade-off. To this end, we present FlowBank, a three-stage framework for portfolio-based agentic workflow optimization. Diversifying proposes DiverseFlow to steer search toward under-covered queries and produce a high-coverage candidate pool. Curating proposes CuraFlow to compress this pool into a compact portfolio with minimal redundancy. Matching casts deployment as edge-value prediction on a query-workflow bipartite graph and routes each incoming query to the portfolio member with the best predicted utility. Across five benchmarks, FlowBank achieves the highest average score among the evaluated methods while remaining cost-competitive, improving over the strongest automated and handcrafted baselines by 4.26% and 14.92% relative, respectively.

Lingzhi Yuan, Chenghao Deng, Fangxu Yu +3

University of Maryland, College Park · Amazon

Multi-Agent LLM SystemsMulti-Agent System OptimizationLarge Language Model-Guided OptimizationAgentic WorkflowsLLM Agent Workflow Optimization
AskPDF