Paper deep dive
Optimize Once, Execute Fast: Latency-Aware Multi-Agent Workflow Learning for Recurrent Queries
Enpei Zhang, Feiyu Qu, Zheng Huang, Dawei Zhou, Elynn Chen, Yujun Yan
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/14/2026, 8:47:19 AM
Summary
The paper introduces LAWA (Latency-Aware Workflow OptimizAtion), a framework for optimizing multi-agent workflows to minimize execution time (makespan) while maintaining downstream task performance. LAWA uses graph editing operations (node removal, parallel rewiring, node permutation) guided by a Graph Evaluator and a Graph Generator to reduce latency in recurrent queries.
Entities (10)
Relation Signals (8)
Dawei Zhou → affiliatedwith → Virginia Tech
confidence 99% · Dawei Zhou Affiliation: Virginia Tech
Enpei Zhang → affiliatedwith → Dartmouth College
confidence 99% · Enpei Zhang Affiliation: Dartmouth College
Elynn Chen → affiliatedwith → New York University
confidence 99% · Elynn Chen Affiliation: New York University
LAWA → optimizes → Makespan
confidence 98% · The objective is to minimize workflow makespan while aiming to retain downstream performance.
LAWA → uses → Graph Evaluator
confidence 95% · LAWA trains a Graph Evaluator that estimates downstream performance of candidate workflows and guides edit selection.
LAWA → uses → Graph Generator
confidence 95% · LAWA trains a Graph Generator that constructs initial chain workflows when no initial workflow is given.
LAWA → employs → Node Removal
confidence 90% · LAWA defines a set of theoretically grounded graph modification operations... Node Removal... eliminates a non-terminal node.
LAWA → employs → Parallel Rewiring
confidence 90% · LAWA defines a set of theoretically grounded graph modification operations... Parallel Rewiring... to increase potential parallelism.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.14481v1
- Canonical: https://arxiv.org/abs/2610.14481v1
Trouble viewing inline? Open PDF directly →
Full Text
104,960 characters extracted from source content.
Expand or collapse full text
Optimize Once, Execute Fast: Latency-Aware Multi-Agent Workflow Learning for Recurrent Queries Enpei Zhang Affiliation: Dartmouth College Email: enpei.zhang.gr@dartmouth.edu Feiyu Qu Affiliation: Dartmouth College Email: feiyu.qu.gr@dartmouth.edu Zheng Huang Affiliation: Dartmouth College Email: zheng.huang.gr@dartmouth.edu Dawei Zhou Affiliation: Virginia Tech Email: yujun.yan@dartmouth.edu Elynn Chen Affiliation: New York University Email: zhoud@vt.edu Yujun Yan Affiliation: Dartmouth College Email: elynn.chen@stern.nyu.edu 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. † Correspondence to enpei.zhang.gr@dartmouth.edu.† Our codes are available at https://github.com/GraphmindDartmouth/LAWA. 1 Introduction Large Language Model-based Multi-Agent Systems (LLM-based MAS) have shown strong capabilities in complex tasks such as code generation and reasoning by coordinating specialized agents through structured, multi-step workflows Yang et al. (2023); Hong et al. (2024). Meanwhile, manually designing such workflows requires substantial effort and domain expertise, motivating recent research on automated workflow generation Zhang et al. (2025d); Li et al. (2025), which allows MAS to automatically customize its workflow for different tasks. However, most prior workflow generation methods still optimize workflows primarily for downstream task performance, while largely overlooking execution time. This limitation is increasingly problematic in LLM-based MAS, where each agent call can incur considerable latency due to model inference and service congestion Chen et al. (2025a), and the overall execution time (makespan) of the workflow can grow rapidly with increasing workflow depth Zhang et al. (2025a). For workflows repeatedly invoked for recurrent queries, small per-query delays can accumulate into substantial latency costs. Such workloads arise in AI customer support, automated software engineering, and cloud troubleshooting Wang et al. (2025a); Hong et al. (2024); Chen et al. (2025b), where similar requests recur and users expect fast responses. Therefore, focusing solely on task performance may lead to workflows that are impractical for real-world deployment. To bridge this gap, we formally propose a new problem: latency-aware workflow generation, where the objective is to minimize makespan while preserving task performance. To solve this problem, we propose LAWA (Latency-Aware Workflow OptimizAtion), a theoretically grounded framework for latency-aware workflow optimization, designed to reduce makespan with monotonicity guarantees while preserving downstream task performance. LAWA is built on three core components: First, we devise a workflow optimization engine that performs makespan-guided beam search over graph edits with theoretical guarantees of monotonic makespan reduction. Second, we train a Graph Evaluator that estimates downstream performance of candidate workflows and guides edit selection toward edits that maintain downstream task performance. Third, we train a Graph Generator that constructs initial chain workflows when no initial workflow is given, enabling LAWA to generate new workflows from scratch. Empirical results across seven benchmarks confirm that LAWA significantly reduces makespan while maintaining competitive task performance. Our contributions are summarized as follows: • New Problem: We define latency-aware workflow generation, where makespan is treated as a primary optimization objective alongside task performance in time-sensitive multi-agent systems. • New Theoretically Grounded Framework: We propose LAWA, a framework that applies theoretically grounded graph editing operations, providing formal guarantees on makespan reduction. • Empirical Validation: We conduct comprehensive experiments across seven benchmarks, demonstrating that LAWA achieves significant makespan reduction compared to state-of-the-art baselines while maintaining competitive task accuracy. 2 Problem Formulation In this section, we formalize the problem of latency-aware workflow optimization. We first introduce the notation for multi-agent workflows and the definition of workflow makespan, and then present our optimization objective. Notations. We model a multi-agent workflow as a directed acyclic graph (DAG), G=(,,)G=(V,A,t), where V is the node set, A is the adjacency matrix, and t is the vector of node latencies. Each node vk∈v_k represents a single agent call with execution time tk>0t_k>0. Different nodes may represent repeated calls to the same agent at different steps. The binary adjacency matrix ∈0,1||×||A∈\0,1\^|V|×|V| encodes directed information dependencies among agent calls: ij=1A_ij=1 indicates that the output of node viv_i is provided as an input context to node vjv_j. We also introduce two special nodes, vIv_I and vOv_O, denoting workflow entry and exit. The entry node vIv_I has no incoming edges, the exit node vOv_O has no outgoing edges, and every other node lies on at least one path from vIv_I to vOv_O. Makespan Definition. Under full parallelism, each node starts immediately after all its predecessors have completed, and the makespan T(G)T(G) (i.e., end-to-end runtime of the workflow) is determined by the critical path (i.e., the path from vIv_I to vOv_O with the maximum cumulative latency). Formally, T(G)=max∑vk∈P∈G(vI,vO)tk, T(G)= _P _G(v_I,v_O) _v_k∈ Pt_k, (1) where G(vI,vO)P_G(v_I,v_O) denotes the set of all paths from the entry node vIv_I to the exit node vOv_O in G. In the main text, we only consider the above definition; an additional experiment with a limited number of executors is reported in Appendix F.4. Optimization Goal. We define the optimization objective for latency-aware workflows as: minGT(G),s.t.S(G)≥S(G0), _G~T(G), .t.~~S(G)≥ S(G_0), (2) where S(G)S(G) denotes the downstream task performance of workflow G, and G0G_0 is the initial graph before modifications. The objective in Equation (2) minimizes the makespan T(G)T(G), while the constraint enforces that the performance of the optimized workflow is no worse than that of the initial graph. In practice, the initial graph can be an existing workflow that meets performance requirements but is latency-inefficient, or a generated initial workflow. 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. 3 Method 3.1 Overview In this section, we introduce LAWA, as shown in Figure 1, a latency-aware workflow generation framework that constructs and optimizes multi-agent workflows through iterative graph modifications. At its core, LAWA defines a set of theoretically grounded graph modification operations that characterize admissible structural changes for reducing makespan under workflow execution constraints. Building on this formulation, LAWA consists of a structural optimization engine and two learnable modules. The structural optimization engine performs a makespan-guided search by iteratively applying valid graph modification operations to reduce workflow makespan. When no initial graph is provided, LAWA includes a Graph Generator, which constructs initial workflows and enables LAWA to operate in a de novo generation setting. To maintain downstream task performance during structural optimization, LAWA trains a Graph Evaluator, which estimates downstream task performance of candidate workflows and guides operation selection. In the following, we first introduce the graph editing operations and their theoretical properties, then present the detailed iterative structural optimization procedure, followed by the graph generator for workflow initialization and the graph evaluator used in the structural optimization. 3.2 Basic Graph Editing Operations We first define a set of graph editing operations that increase parallelism, remove redundant agents, and reorder agent execution, respectively. Definition 3.1 (Parallel Rewiring). Given two nodes i and j with ij>0A_ij>0, the parallel rewiring operation removes the dependency from i to j and merges their outgoing and incoming edges to increase potential parallelism. Formally, we define the operator ParallelRewire(G,i,j)ParallelRewire(G,i,j) as: ij←0;ik←1for all k that jk=1;kj←1for all k that ki=1 _ij← 0\;; _ik← 1\;for all $k$ that $ A_jk=1$\;; _kj← 1\;for all $k$ that $ A_ki=1$ (3) Definition 3.2 (Node Removal). The node removal operation eliminates a non-terminal node k∈∖vI,vOk \v_I,v_O\ from the workflow while preserving connectivity by linking its predecessors and successors. Formally, we define the operator RemoveNode(G,k)RemoveNode(G,k) as: ij _ij ←1for all (i,j) that ik=1 and kj=1; ← 1 all $(i,j)$ that $ A_ik=1$ and $A_kj=1$\;; (4) ik _ik ←0for all i that ik=1; ← 0 all $i$ that $ A_ik=1$\;; (5) kj _kj ←0for all j that kj=1. ← 0 all $j$ that $ A_kj=1$\;. (6) Definition 3.3 (Node Permutation). Let σ:→σ:V be a permutation over the node set. We define the induced permutation operator Πσ _σ acting on adjacency matrix A as (Πσ())σ(u),σ(v)=u,v∀u,v∈, ( _σ(A) )_σ(u),\,σ(v)\;=\;A_u,v ∀\,u,v , (7) which reorders nodes in the workflow. The proposed graph operations are designed to satisfy three requirements. First, the operations preserve workflow connectivity. Second, the operations monotonically reduce workflow makespan. Finally, under a suitable node ordering, the operator set is expressive enough to transform a chain into any transitively reduced DAG considered in our formulation. The following theorems establish these guarantees. Theorem 3.4 (Reachability). Let u↝Gvu _Gv denote that there exists a directed path from u to v in G. Let G′G denote the graph obtained from G after applying one of the operations: (i) Node Removal. Let k∈∖vI,vOk \v_I,v_O\ be a removed node. Then, ∀u,v∈∖k,u↝Gv⇔u↝G′v.∀ u,v \k\, u _Gv\; \;u _G v. (8) (i) Parallel Rewiring. Let (i,j)(i,j) be the rewired edge. Then, ∀u,v∈∖i,j,u↝Gv⇔u↝G′v.∀ u,v \i,j\, u _Gv\; \;u _G v. (9) Proof is presented in Appendix A.1. Theorem 3.5 (Non-increasing Makespan). Let G=(,,)G=(V,A,t) be a workflow DAG. Let G′G denote the graph obtained from G by applying either the Node Removal operation to a node k∈∖vI,vOk \v_I,v_O\ or the Parallel Rewiring operation to an existing edge (i,j)(i,j). Then T(G′)≤T(G).T(G )≤ T(G). Proof is presented in Appendix A.2. Theorem 3.6 (Completeness). Let GchainG_chain be an arbitrary chain DAG over all nodes in V with adjacency matrix chainA_chain. For any target DAG G∗=(,∗)G =(V,A ) that is transitively reduced, there exist a node permutation σ and a finite operation sequence O consisting only of Parallel Rewiring and Node Removal such that (Πσ(chain))=∗.O\! ( _σ(A_chain) )\;=\;A . Proof is presented in Appendix A.3. Together, Theorems 3.4 and 3.5 motivate Parallel Rewiring and Node Removal as graph-modification operators that preserve workflow connectivity and do not increase makespan. Theorem 3.6 further indicates that the edit operators are expressive enough, in principle, to transform a chain into any transitively reduced DAG under a suitable node ordering, and the Graph Generator (Section 3.4) is designed to learn initial chain workflows with such suitable node orderings. 3.3 Latency-Aware Structural Optimization Algorithm 1 Latency-Aware Structural Optimization 0: Optional initial graph G0G_0, beam size B, max iterations K. 1: Initialize pretrained Graph Generator ϕG_φ and pretrained Graph Evaluator SθS_θ 2: Set G0←ϕ()G_0 _φ() if G0=∅G_0= 3: Initialize candidate set ←G0C←\G_0\ 4: for k=1k=1 to K do 5: for all G∈G do 6: Construct candidates by Node Removal: ←∪RemoveNode(G,u)∣u∈(G)∖vI,vOC ∪\RemoveNode(G,u) u (G) \v_I,v_O\\ 7: Compute rwrR^rwr by Equation 15 8: for all edge (u,v)(u,v) with u,vrwr≥0R^rwr_u,v\!≥\!0 do 9: Construct candidates by Parallel rewiring: ←∪ParallelRewire(G,u,v)C ∪\ParallelRewire(G,u,v)\ 10: end for 11: end for 12: Performance-Based filtering: ←G′∈∣Sθ(G′)≥Sθ(G0)C←\G S_θ(G )≥ S_θ(G_0)\ 13: Candidate update by runtime-first ranking: ←Top-BT(⋅)()C -B_T(·)(C) 14: end for 15: Select final solution: G∗←argminG∈(T(G)) G ← _G (T(G) ) 15: Optimized workflow G∗G . Based on the graph editing operations defined above, we now describe the procedure for latency-aware structural optimization in LAWA, which operates in two stages. Workflow Initialization. LAWA initializes workflows in two ways: it either refines an existing workflow graph, or constructs an initial graph using the Graph Generator when no prior structure is available. The Graph Generator produces chain-structured graphs, motivated by the expressivity result in Theorem 3.6. These two modes allow LAWA to function both as a plug-in optimizer for existing workflows and as a de novo workflow generator. Iterative Structural Optimization. In the second stage, LAWA refines workflow structure via a guided beam search to reduce makespan (Algorithm 1). Before the search, we first estimate node latencies tkt_k by calibration runs (e.g., each agent’s P95 response time on a calibration set). At each beam-search iteration, LAWA follows a three-stage procedure. First, for each workflow G∈G , LAWA generates new candidates by applying one step of Node Removal or Parallel Rewiring. Node Removal is applied to every non-terminal node in G excluding vIv_I and vOv_O. For Parallel Rewiring, to reduce the number of candidates, we apply it only to edges (u,v)(u,v) with u,vrwr≥0R^rwr_u,v≥ 0, where u,vrwrR^rwr_u,v is the approximate change in downstream task performance induced by rewiring (u,v)(u,v). Parallel Rewiring is disallowed for node pairs invoking the same agent, as such nodes cannot be executed in parallel in reality. Second, LAWA evaluates each candidate workflow G′∈G using a Graph Evaluator Sθ(⋅)S_θ(·) and retains only those satisfying the baseline performance constraint Sθ(G′)≥Sθ(G0)S_θ(G )≥ S_θ(G_0). Finally, LAWA keeps the Top-B retained workflows with the smallest makespan T(G)T(G) as the candidate set C for the next iteration. To avoid repeatedly executing candidate workflows, the Graph Evaluator is used to predict downstream task performance; u,vrwrR^rwr_u,v is computed from its gradient information. 3.4 Graph Generator for Initialization The Graph Generator provides an initial chain-structured workflow when no prior structure is available. For each agent node u, we first construct an embedding ue_u by encoding the agent role and system prompt with a frozen Sentence-BERT encoder. We formulate workflow initialization as an auto-regressive sequence generation problem, where each token corresponds to the agent embedding ue_u, and the model predicts the next token (agent) ata_t according to current sequence a<ta_<t, producing an ordered agent sequence that defines a chain workflow. Graph Generator Architecture. The Graph Generator adopts a transformer encoder ℛϕR_φ for auto-regressive sequence generation. Given a partial agent sequence a<ta_<t, the encoder produces a contextual hidden representation t=ℛϕ(a<t)∈ℝdh_t=R_φ(a_<t) ^d. The model predicts the next agent ata_t by computing a similarity-based distribution between th_t and the agent embedding matrix E: Pϕ(at∣a<t)=Softmax(t⋅⊤d), P_φ(a_t a_<t)=Softmax\! ( h_t·E d ), (10) During generation, the entry node is used as the initial token, and generation terminates when the exit node is produced. Graph Generator Training. We train ℛϕR_φ using a two-stage strategy consisting of supervised pre-training and preference alignment. We use a graph dataset =(G,s(G))D=\(G,s(G))\, where s(G)s(G) is the empirical performance of workflow G evaluated on the held-out training set for the corresponding task. From D, we retain highest-scoring graphs highD_high for supervised learning. For each G∈highG _high, we sample sequences y=(a1,…,aL)y=(a_1,…,a_L) such that for any indices 1≤i<j≤L1≤ i<j≤ L, the corresponding node of aia_i in G is not reachable from that of aja_j, and minimize the negative log-likelihood: ℒSFT(ϕ)=−y∼high∑t=1LlogPϕ(at∣a<t). _SFT(φ)=-E_y _high _t=1^L P_φ(a_t a_<t). (11) To further align generation with workflow performance, we also apply DPO. Preference pairs (yw,yl)(y_w,y_l) are constructed from graph Gw,Gl∈G_w,G_l with s(Gw)>s(Gl)s(G_w)>s(G_l), and ℛϕR_φ is trained using the DPO loss: ℒDPO(ϕ) _DPO(φ) =−(yw,yl)[logσ(βlogPϕ(yw)Pref(yw)−βlogPϕ(yl)Pref(yl))], =-E_(y_w,y_l) [ σ\! (β P_φ(y_w)P_ref(y_w)-β P_φ(y_l)P_ref(y_l) ) ], (12) where PrefP_ref is the frozen SFT model and β controls deviation from the reference policy. 3.5 Graph Evaluator for Performance Prediction The Graph Evaluator is a supervised model that maps a workflow graph G to a scalar score Sθ(G)∈ℝS_θ(G) to estimate the downstream task performance. As only the relative performance of the workflow matters, we train it using preference ranking instead of regression. Graph Evaluator Architecture. We implement the Graph Evaluator SθS_θ as a graph neural network (GNN) over the workflow DAG. Each node u∈u is initialized with the agent embedding ue_u defined in Section 3.4. The node embeddings are propagated through GNN message-passing layers and then pooled to obtain a graph-level representation, which is mapped to a scalar score by an MLP head: Sθ(G)=MLP(Pool(GNN(,u))).S_θ(G)=MLP\! (Pool (GNN(A,\e_u\) ) ). (13) Graph Evaluator Training. We train the Graph Evaluator using a preference-based objective. Specifically, we reuse the graph dataset D defined in Section 3.4. From D, we construct preference pairs (Gw,Gl)(G_w,G_l) such that s(Gw)>s(Gl)s(G_w)>s(G_l). We then train the Graph Evaluator SθS_θ using a pairwise preference objective inspired by Direct Preference Optimization (DPO) Rafailov et al. (2023), which encourages higher scores for preferred workflows: ℒpairwise=−logσ(β(Δπ−Δref)), _pairwise=- σ\! (β( _π- _ref) ), (14) where σ(⋅)σ(·) is the sigmoid function; β∈ℝβ is a hyperparameter; Δπ=Sθ(Gw)−Sθ(Gl) _π=S_θ(G_w)-S_θ(G_l) denotes the predicted score difference; and Δref _ref is provided by a reference model (e.g., current best model on the validation set). Gradient-Based Approximation for Edge Editing. To filter out rewiring operations that are unlikely to improve downstream task performance, we approximate the performance change of Parallel Rewiring using first-order gradients of the Graph Evaluator with respect to the workflow adjacency matrix A. Let =∂Sθ/∂ =∂ S_θ/ denote the gradient of the Graph Evaluator with respect to A. For each potential rewiring (i,j)(i,j), the induced score change is approximated by the matrix inner product ⟨,Δ⟩ , , where Δ represents the change of A after the rewiring. The score change of all edges can be approximated by: rwr=−+~⊤+⊤~, ^rwr=-\,H\;+\; H\,A \;+\;A H, (15) where =⊙H= , ~=⊙(1−) H= (1-A), ⊙ denotes the Hadamard product, and i,jrwrR^rwr_i,j represents the estimated score change of rewiring edge (i,j)(i,j). The derivations are provided in Appendix B. We further provide a theoretical analysis of a perturbed Graph Evaluator in Appendix E, showing that LAWA can still preserve performance with high probability under mild evaluator decision errors. 4 Experiments In this section, we conduct extensive experiments to evaluate LAWA through four research questions. (RQ1) How does LAWA, as a workflow generation framework, compare to prior methods in generating workflows? (RQ2) Can LAWA, when used as a plug-in module, reduce workflow makespan while preserving performance? (RQ3) How robust is LAWA when Graph Evaluator decisions are inaccurate or perturbed? (RQ4) How do the individual components of LAWA contribute to its latency and performance? Additional experiments are provided in Appendix F. 4.1 Experimental Setup Benchmarks. We conduct evaluations across seven benchmarks spanning three domains. The code generation domain includes MBPP and HumanEval Austin et al. (2021); Chen and others (2021). The mathematical reasoning domain includes GSM8K, MATH500, SVAMP, and AQuA Cobbe et al. (2021); Hendrycks et al. (2021b); Patel et al. (2021); Ling et al. (2017). The general knowledge domain is evaluated using MMLU Hendrycks et al. (2021a). For each benchmark, we reserve a small subset of samples for training the proposed method and baselines, and hold them out from evaluation (see Appendix C). Baselines. We compare LAWA against state-of-the-art dynamic multi-agent frameworks, including DyLAN Liu et al. (2024), G-Designer Zhang et al. (2025c), AgentDropout Wang et al. (2025b), AgentPrune Zhang et al. (2025b), and BiRouter Yang et al. (2025b), as well as the accuracy-oriented workflow generator AFlow Zhang et al. (2025d), and the latency-aware framework LAMaS Shi et al. (2026). In addition, we include three basic workflow topologies: (1) Random Chain, which randomly permutes all available agents into a sequential structure; (2) Random Graph, which constructs a directed acyclic graph (DAG) using all agents, where edges are sampled with probability p=0.5p=0.5 while enforcing acyclicity; and (3) 3-Round Discussion, which simulates a round-table discussion where all agents execute in parallel for three rounds, with the full context of the previous round broadcast to all agents in the subsequent round. Agent Backbones. For a fair comparison, all methods use the same pool of agents built on Qwen3-30B-A3B-Instruct-2507 Yang et al. (2025a). Each agent is configured with different roles and functionalities. Across task domains, each method can access 8 candidate agents for coding, 10 for general knowledge, and 11 for mathematical reasoning. Additional details are provided in Appendix C. Wall-Clock Makespan Measurement. We report real end-to-end wall-clock makespan per query under the same computational budget; detailed settings are provided in Appendix C. For LAWA, the tkt_k used during optimization is estimated as each agent’s P95 response time on training-set queries. Table 1: Real wall-clock makespan (Seconds↓ ) 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±std_ [rgb]0.3,0.3,0.3 . 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. Method MBPP HumanEval AQuA GSM8K MATH500 SVAMP MMLU Avg. Rank Rand. Graph 16.92±1.5316.92_ [rgb]0.3,0.3,0.3± 1.53 19.80±1.4819.80_ [rgb]0.3,0.3,0.3± 1.48 24.16±0.4224.16_ [rgb]0.3,0.3,0.3± 0.42 17.13±1.2417.13_ [rgb]0.3,0.3,0.3± 1.24 26.33±1.4126.33_ [rgb]0.3,0.3,0.3± 1.41 17.24±1.1217.24_ [rgb]0.3,0.3,0.3± 1.12 18.47±0.4318.47_ [rgb]0.3,0.3,0.3± 0.43 8.868.86 Rand. Chain 22.67±1.5222.67_ [rgb]0.3,0.3,0.3± 1.52 22.26±0.9422.26_ [rgb]0.3,0.3,0.3± 0.94 31.34±2.6531.34_ [rgb]0.3,0.3,0.3± 2.65 27.90±0.0827.90_ [rgb]0.3,0.3,0.3± 0.08 36.86±0.2936.86_ [rgb]0.3,0.3,0.3± 0.29 23.54±0.2523.54_ [rgb]0.3,0.3,0.3± 0.25 24.06±0.2224.06_ [rgb]0.3,0.3,0.3± 0.22 10.5710.57 3-Round Disc. 17.52±2.8417.52_ [rgb]0.3,0.3,0.3± 2.84 15.08±0.7115.08_ [rgb]0.3,0.3,0.3± 0.71 17.04±0.6117.04_ [rgb]0.3,0.3,0.3± 0.61 15.06±0.1015.06_ [rgb]0.3,0.3,0.3± 0.10 21.04±0.9421.04_ [rgb]0.3,0.3,0.3± 0.94 13.60±0.7613.60_ [rgb]0.3,0.3,0.3± 0.76 13.93±0.1313.93_ [rgb]0.3,0.3,0.3± 0.13 7.297.29 DyLAN 11.46±1.3411.46_ [rgb]0.3,0.3,0.3± 1.34 11.29±0.08 blue!15 [rgb]0,0,011.29_ [rgb]0.3,0.3,0.3± 0.08 13.65±1.1013.65_ [rgb]0.3,0.3,0.3± 1.10 8.09±0.19 blue!15 [rgb]0,0,08.09_ [rgb]0.3,0.3,0.3± 0.19 16.63±0.2316.63_ [rgb]0.3,0.3,0.3± 0.23 9.38±0.619.38_ [rgb]0.3,0.3,0.3± 0.61 9.11±0.269.11_ [rgb]0.3,0.3,0.3± 0.26 3.143.14 G-Designer 25.27±1.7525.27_ [rgb]0.3,0.3,0.3± 1.75 24.01±1.2824.01_ [rgb]0.3,0.3,0.3± 1.28 15.56±0.2615.56_ [rgb]0.3,0.3,0.3± 0.26 9.74±0.559.74_ [rgb]0.3,0.3,0.3± 0.55 21.34±9.4621.34_ [rgb]0.3,0.3,0.3± 9.46 23.47±4.0823.47_ [rgb]0.3,0.3,0.3± 4.08 25.32±2.4325.32_ [rgb]0.3,0.3,0.3± 2.43 9.439.43 AgentDropout 13.92±5.5613.92_ [rgb]0.3,0.3,0.3± 5.56 14.24±3.7314.24_ [rgb]0.3,0.3,0.3± 3.73 13.85±0.4213.85_ [rgb]0.3,0.3,0.3± 0.42 9.57±0.959.57_ [rgb]0.3,0.3,0.3± 0.95 21.54±7.5821.54_ [rgb]0.3,0.3,0.3± 7.58 16.72±2.8016.72_ [rgb]0.3,0.3,0.3± 2.80 17.31±4.2117.31_ [rgb]0.3,0.3,0.3± 4.21 6.146.14 AgentPrune 20.18±2.5420.18_ [rgb]0.3,0.3,0.3± 2.54 18.28±1.2418.28_ [rgb]0.3,0.3,0.3± 1.24 14.56±2.1514.56_ [rgb]0.3,0.3,0.3± 2.15 9.20±0.089.20_ [rgb]0.3,0.3,0.3± 0.08 19.25±2.1219.25_ [rgb]0.3,0.3,0.3± 2.12 18.75±0.6918.75_ [rgb]0.3,0.3,0.3± 0.69 19.01±1.4419.01_ [rgb]0.3,0.3,0.3± 1.44 7.297.29 BiRouter 13.54±0.8513.54_ [rgb]0.3,0.3,0.3± 0.85 17.40±3.5117.40_ [rgb]0.3,0.3,0.3± 3.51 14.19±2.1514.19_ [rgb]0.3,0.3,0.3± 2.15 9.95±1.129.95_ [rgb]0.3,0.3,0.3± 1.12 18.64±1.2018.64_ [rgb]0.3,0.3,0.3± 1.20 8.93±0.548.93_ [rgb]0.3,0.3,0.3± 0.54 12.17±1.6712.17_ [rgb]0.3,0.3,0.3± 1.67 5.575.57 AFlow 10.24±1.7910.24_ [rgb]0.3,0.3,0.3± 1.79 14.49±2.8614.49_ [rgb]0.3,0.3,0.3± 2.86 15.53±1.2715.53_ [rgb]0.3,0.3,0.3± 1.27 9.51±0.579.51_ [rgb]0.3,0.3,0.3± 0.57 18.55±1.0318.55_ [rgb]0.3,0.3,0.3± 1.03 8.63±0.848.63_ [rgb]0.3,0.3,0.3± 0.84 11.00±1.2911.00_ [rgb]0.3,0.3,0.3± 1.29 4.434.43 LAMaS 8.82±0.97 orange!20 [rgb]0,0,08.82_ [rgb]0.3,0.3,0.3± 0.97 11.87±1.3811.87_ [rgb]0.3,0.3,0.3± 1.38 9.92±2.37 blue!15 [rgb]0,0,09.92_ [rgb]0.3,0.3,0.3± 2.37 8.78±1.808.78_ [rgb]0.3,0.3,0.3± 1.80 11.85±1.16 blue!15 [rgb]0,0,011.85_ [rgb]0.3,0.3,0.3± 1.16 8.12±0.88 blue!15 [rgb]0,0,08.12_ [rgb]0.3,0.3,0.3± 0.88 8.39±0.24 blue!15 [rgb]0,0,08.39_ [rgb]0.3,0.3,0.3± 0.24 2.14 LAWA 8.84±0.79 blue!15 [rgb]0,0,08.84_ [rgb]0.3,0.3,0.3± 0.79 11.26±1.03 orange!20 [rgb]0,0,011.26_ [rgb]0.3,0.3,0.3± 1.03 9.86±0.38 orange!20 [rgb]0,0,09.86_ [rgb]0.3,0.3,0.3± 0.38 7.30±0.10 orange!20 [rgb]0,0,07.30_ [rgb]0.3,0.3,0.3± 0.10 11.80±0.48 orange!20 [rgb]0,0,011.80_ [rgb]0.3,0.3,0.3± 0.48 6.18±0.56 orange!20 [rgb]0,0,06.18_ [rgb]0.3,0.3,0.3± 0.56 7.86±1.28 orange!20 [rgb]0,0,07.86_ [rgb]0.3,0.3,0.3± 1.28 1.14 Table 2: Comparison of task performance (Accuracy↑ ) 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_ . 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. Method MBPP HumanEval AQuA GSM8K MATH500 SVAMP MMLU Avg. Rank Rand. Graph 63.94±0.4963.94_ [rgb]0.3,0.3,0.3± 0.49 92.07±2.9992.07_ [rgb]0.3,0.3,0.3± 2.99 80.58±0.6780.58_ [rgb]0.3,0.3,0.3± 0.67 93.23±0.2093.23_ [rgb]0.3,0.3,0.3± 0.20 66.53±0.4166.53_ [rgb]0.3,0.3,0.3± 0.41 93.67±0.6293.67_ [rgb]0.3,0.3,0.3± 0.62 65.33±4.9465.33_ [rgb]0.3,0.3,0.3± 4.94 7.367.36 Rand. Chain 64.07±0.7364.07_ [rgb]0.3,0.3,0.3± 0.73 91.67±0.7691.67_ [rgb]0.3,0.3,0.3± 0.76 80.31±0.6480.31_ [rgb]0.3,0.3,0.3± 0.64 93.91±1.1593.91_ [rgb]0.3,0.3,0.3± 1.15 66.47±0.5766.47_ [rgb]0.3,0.3,0.3± 0.57 93.30±0.3793.30_ [rgb]0.3,0.3,0.3± 0.37 64.11±5.6064.11_ [rgb]0.3,0.3,0.3± 5.60 8.008.00 3-Round Disc. 64.33±1.1264.33_ [rgb]0.3,0.3,0.3± 1.12 92.89±0.7692.89_ [rgb]0.3,0.3,0.3± 0.76 72.57±0.9872.57_ [rgb]0.3,0.3,0.3± 0.98 94.77±0.2194.77_ [rgb]0.3,0.3,0.3± 0.21 63.80±0.2863.80_ [rgb]0.3,0.3,0.3± 0.28 94.27±0.29 orange!20 [rgb]0,0,094.27_ [rgb]0.3,0.3,0.3± 0.29 65.66±0.2965.66_ [rgb]0.3,0.3,0.3± 0.29 6.646.64 DyLAN 64.72±1.0264.72_ [rgb]0.3,0.3,0.3± 1.02 93.29±1.32 blue!15 [rgb]0,0,093.29_ [rgb]0.3,0.3,0.3± 1.32 80.71±0.9680.71_ [rgb]0.3,0.3,0.3± 0.96 95.80±0.2395.80_ [rgb]0.3,0.3,0.3± 0.23 65.87±0.4165.87_ [rgb]0.3,0.3,0.3± 0.41 93.67±0.2493.67_ [rgb]0.3,0.3,0.3± 0.24 68.03±0.0968.03_ [rgb]0.3,0.3,0.3± 0.09 4.794.79 G-Designer 63.81±1.1063.81_ [rgb]0.3,0.3,0.3± 1.10 89.84±0.7689.84_ [rgb]0.3,0.3,0.3± 0.76 76.77±1.7976.77_ [rgb]0.3,0.3,0.3± 1.79 94.16±0.3394.16_ [rgb]0.3,0.3,0.3± 0.33 66.13±1.0966.13_ [rgb]0.3,0.3,0.3± 1.09 94.20±0.2994.20_ [rgb]0.3,0.3,0.3± 0.29 67.71±0.1767.71_ [rgb]0.3,0.3,0.3± 0.17 7.717.71 AgentDropout 64.59±1.9164.59_ [rgb]0.3,0.3,0.3± 1.91 91.06±2.2491.06_ [rgb]0.3,0.3,0.3± 2.24 80.84±1.3080.84_ [rgb]0.3,0.3,0.3± 1.30 93.58±0.8393.58_ [rgb]0.3,0.3,0.3± 0.83 66.47±0.0966.47_ [rgb]0.3,0.3,0.3± 0.09 93.27±0.6593.27_ [rgb]0.3,0.3,0.3± 0.65 65.97±2.1565.97_ [rgb]0.3,0.3,0.3± 2.15 7.077.07 AgentPrune 64.46±0.6664.46_ [rgb]0.3,0.3,0.3± 0.66 90.45±2.2490.45_ [rgb]0.3,0.3,0.3± 2.24 79.13±3.3679.13_ [rgb]0.3,0.3,0.3± 3.36 94.06±0.4394.06_ [rgb]0.3,0.3,0.3± 0.43 67.33±0.77 orange!20 [rgb]0,0,067.33_ [rgb]0.3,0.3,0.3± 0.77 94.20±0.5794.20_ [rgb]0.3,0.3,0.3± 0.57 72.12±5.6672.12_ [rgb]0.3,0.3,0.3± 5.66 5.645.64 BiRouter 63.81±0.8463.81_ [rgb]0.3,0.3,0.3± 0.84 92.48±0.7692.48_ [rgb]0.3,0.3,0.3± 0.76 82.15±1.9482.15_ [rgb]0.3,0.3,0.3± 1.94 95.05±0.2895.05_ [rgb]0.3,0.3,0.3± 0.28 66.73±0.3866.73_ [rgb]0.3,0.3,0.3± 0.38 93.90±1.0093.90_ [rgb]0.3,0.3,0.3± 1.00 65.09±0.6465.09_ [rgb]0.3,0.3,0.3± 0.64 5.935.93 AFlow 65.24±0.22 blue!15 [rgb]0,0,065.24_ [rgb]0.3,0.3,0.3± 0.22 93.70±0.93 orange!20 [rgb]0,0,093.70_ [rgb]0.3,0.3,0.3± 0.93 83.20±0.23 blue!15 [rgb]0,0,083.20_ [rgb]0.3,0.3,0.3± 0.23 96.06±0.95 orange!20 [rgb]0,0,096.06_ [rgb]0.3,0.3,0.3± 0.95 66.80±0.6966.80_ [rgb]0.3,0.3,0.3± 0.69 92.13±0.8392.13_ [rgb]0.3,0.3,0.3± 0.83 76.04±1.48 blue!15 [rgb]0,0,076.04_ [rgb]0.3,0.3,0.3± 1.48 3.14 LAMaS 64.98±0.3964.98_ [rgb]0.3,0.3,0.3± 0.39 91.67±0.9391.67_ [rgb]0.3,0.3,0.3± 0.93 79.53±5.0579.53_ [rgb]0.3,0.3,0.3± 5.05 92.12±1.1492.12_ [rgb]0.3,0.3,0.3± 1.14 65.33±1.6765.33_ [rgb]0.3,0.3,0.3± 1.67 92.70±2.1792.70_ [rgb]0.3,0.3,0.3± 2.17 66.99±1.7166.99_ [rgb]0.3,0.3,0.3± 1.71 7.937.93 LAWA 66.28±0.37 orange!20 [rgb]0,0,066.28_ [rgb]0.3,0.3,0.3± 0.37 92.89±1.0492.89_ [rgb]0.3,0.3,0.3± 1.04 83.46±0.85 orange!20 [rgb]0,0,083.46_ [rgb]0.3,0.3,0.3± 0.85 96.03±0.20 blue!15 [rgb]0,0,096.03_ [rgb]0.3,0.3,0.3± 0.20 67.00±0.86 blue!15 [rgb]0,0,067.00_ [rgb]0.3,0.3,0.3± 0.86 94.23±0.21 blue!15 [rgb]0,0,094.23_ [rgb]0.3,0.3,0.3± 0.21 77.77±3.15 orange!20 [rgb]0,0,077.77_ [rgb]0.3,0.3,0.3± 3.15 1.79 4.2 RQ1: LAWA as a Workflow Generator We first evaluate the effectiveness of LAWA as a workflow generator by comparing it with prior methods in terms of both execution efficiency and downstream task performance. In this setting, LAWA uses the Graph Generator to initialize workflows. To mitigate randomness, we execute all methods across 3 independent runs and report average results. Makespan Analysis. Table 1 reports real wall-clock makespan of generated workflows across seven benchmarks. LAWA is the fastest method on six of seven benchmarks and is only 0.02s slower than LAMaS on MBPP, while outperforming LAMaS in task accuracy on all seven benchmarks (Table 2). LAWA is also efficient to obtain: since the search operates on graph structures without executing agents, its one-time search and evaluator-training cost is recovered within a few recurrent executions, and even with graph-dataset construction included, the full pipeline remains substantially faster than the on-policy AgentDropout (Appendix F.2). To intuitively demonstrate why LAWA achieves lower makespan, Figure 2 visualizes three example workflow topologies and corresponding Gantt charts produced by representative methods on the MBPP benchmark. DyLAN adopts a layered, neural-network-like execution pattern that enables high parallelism within each round but enforces strict inter-round synchronization. This causes each round to wait for the slowest agent in the previous layer, leading to higher overall makespan. Another baseline, AgentPrune, simplifies workflows by pruning nodes and edges but does not explicitly target critical-path bottlenecks, often leaving a long critical path that dominates end-to-end makespan. In contrast, LAWA produces workflows with shorter critical paths. We include a case study on how LAWA reduces the critical path in Appendix D. Performance Analysis. Table 2 summarizes task performance across all benchmarks. Despite aggressively optimizing workflow topology for makespan reduction, LAWA consistently maintains comparable or superior accuracy to the state-of-the-art baselines, achieving the best average rank among all methods, including the strong accuracy-oriented AFlow. These results show that, as a workflow generation method, LAWA can produce workflow graphs that achieve both low makespan and strong downstream performance. We also report total token consumption in Appendix F.1, where LAWA still remains token-efficient, and results with the frontier model Kimi-K2.6 in Appendix F.3. 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. 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_ ) 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 Random Graph Random Chain AgentPrune AgentDropout Acc (%) Makespan (s) Acc (%) Makespan (s) Acc (%) Makespan (s) Acc (%) Makespan (s) HumanEval +1.63±3.53+1.63_ [rgb]0.3,0.3,0.3± 3.53 -4.40±0.97-4.40_ [rgb]0.3,0.3,0.3± 0.97 +0.20±0.57+0.20_ [rgb]0.3,0.3,0.3± 0.57 -7.61±0.04-7.61_ [rgb]0.3,0.3,0.3± 0.04 +1.42±1.88+1.42_ [rgb]0.3,0.3,0.3± 1.88 -2.79±0.46-2.79_ [rgb]0.3,0.3,0.3± 0.46 +0.81±2.35+0.81_ [rgb]0.3,0.3,0.3± 2.35 -2.19±1.56-2.19_ [rgb]0.3,0.3,0.3± 1.56 MBPP +0.26±0.49+0.26_ [rgb]0.3,0.3,0.3± 0.49 -5.39±1.49-5.39_ [rgb]0.3,0.3,0.3± 1.49 +0.39±0.84+0.39_ [rgb]0.3,0.3,0.3± 0.84 -6.86±0.06-6.86_ [rgb]0.3,0.3,0.3± 0.06 +0.91±1.20+0.91_ [rgb]0.3,0.3,0.3± 1.20 -2.41±0.72-2.41_ [rgb]0.3,0.3,0.3± 0.72 +0.13±1.63+0.13_ [rgb]0.3,0.3,0.3± 1.63 -2.75±0.73-2.75_ [rgb]0.3,0.3,0.3± 0.73 AQuA +0.52±0.74+0.52_ [rgb]0.3,0.3,0.3± 0.74 -4.92±1.59-4.92_ [rgb]0.3,0.3,0.3± 1.59 +0.52±0.19+0.52_ [rgb]0.3,0.3,0.3± 0.19 -8.05±0.11-8.05_ [rgb]0.3,0.3,0.3± 0.11 +1.84±3.17+1.84_ [rgb]0.3,0.3,0.3± 3.17 -3.65±0.06-3.65_ [rgb]0.3,0.3,0.3± 0.06 +0.79±1.96+0.79_ [rgb]0.3,0.3,0.3± 1.96 -3.21±0.12-3.21_ [rgb]0.3,0.3,0.3± 0.12 GSM8K +0.25±0.25+0.25_ [rgb]0.3,0.3,0.3± 0.25 -6.16±1.33-6.16_ [rgb]0.3,0.3,0.3± 1.33 +0.08±1.07+0.08_ [rgb]0.3,0.3,0.3± 1.07 -8.17±0.01-8.17_ [rgb]0.3,0.3,0.3± 0.01 +0.08±0.75+0.08_ [rgb]0.3,0.3,0.3± 0.75 -3.06±0.43-3.06_ [rgb]0.3,0.3,0.3± 0.43 +1.26±1.26+1.26_ [rgb]0.3,0.3,0.3± 1.26 -2.78±0.24-2.78_ [rgb]0.3,0.3,0.3± 0.24 MATH500 +0.47±1.57+0.47_ [rgb]0.3,0.3,0.3± 1.57 -6.63±0.57-6.63_ [rgb]0.3,0.3,0.3± 0.57 +0.47±0.57+0.47_ [rgb]0.3,0.3,0.3± 0.57 -8.66±0.16-8.66_ [rgb]0.3,0.3,0.3± 0.16 +0.07±0.90+0.07_ [rgb]0.3,0.3,0.3± 0.90 -3.35±0.42-3.35_ [rgb]0.3,0.3,0.3± 0.42 +0.13±0.52+0.13_ [rgb]0.3,0.3,0.3± 0.52 -3.71±0.13-3.71_ [rgb]0.3,0.3,0.3± 0.13 SVAMP +1.23±0.78+1.23_ [rgb]0.3,0.3,0.3± 0.78 -5.53±1.43-5.53_ [rgb]0.3,0.3,0.3± 1.43 +0.03±0.21+0.03_ [rgb]0.3,0.3,0.3± 0.21 -8.17±0.01-8.17_ [rgb]0.3,0.3,0.3± 0.01 +0.03±1.01+0.03_ [rgb]0.3,0.3,0.3± 1.01 -3.70±0.33-3.70_ [rgb]0.3,0.3,0.3± 0.33 +0.63±0.69+0.63_ [rgb]0.3,0.3,0.3± 0.69 -2.92±0.73-2.92_ [rgb]0.3,0.3,0.3± 0.73 MMLU +1.94±5.88+1.94_ [rgb]0.3,0.3,0.3± 5.88 -4.61±0.33-4.61_ [rgb]0.3,0.3,0.3± 0.33 +3.26±3.87+3.26_ [rgb]0.3,0.3,0.3± 3.87 -8.62±0.29-8.62_ [rgb]0.3,0.3,0.3± 0.29 +0.02±1.10+0.02_ [rgb]0.3,0.3,0.3± 1.10 -3.14±0.13-3.14_ [rgb]0.3,0.3,0.3± 0.13 +0.11±5.74+0.11_ [rgb]0.3,0.3,0.3± 5.74 -3.48±0.58-3.48_ [rgb]0.3,0.3,0.3± 0.58 Table 4: RQ3: Robustness under evaluator perturbations. We flip the evaluator’s keep/reject decision with probability α, and report the task accuracy (%) of the generated workflows as mean±std_ [rgb]0.3,0.3,0.3 . Performance remains close to the unperturbed setting for small flip rates (α≤0.2α≤ 0.2). Dataset α=0.00 α=0.10 α=0.20 HumanEval 92.89±1.0492.89_ [rgb]0.3,0.3,0.3± 1.04 92.48±0.3592.48_ [rgb]0.3,0.3,0.3± 0.35 91.67±1.5391.67_ [rgb]0.3,0.3,0.3± 1.53 MBPP 66.28±0.3766.28_ [rgb]0.3,0.3,0.3± 0.37 66.28±0.5966.28_ [rgb]0.3,0.3,0.3± 0.59 65.76±0.6765.76_ [rgb]0.3,0.3,0.3± 0.67 AQuA 83.46±0.8583.46_ [rgb]0.3,0.3,0.3± 0.85 83.34±0.8283.34_ [rgb]0.3,0.3,0.3± 0.82 82.83±1.3882.83_ [rgb]0.3,0.3,0.3± 1.38 MATH500 67.00±0.8667.00_ [rgb]0.3,0.3,0.3± 0.86 66.73±0.3166.73_ [rgb]0.3,0.3,0.3± 0.31 65.87±0.2365.87_ [rgb]0.3,0.3,0.3± 0.23 Table 5: RQ4: Component ablations. Changes in accuracy (%) and makespan (s) relative to full LAWA. Removing any component reduces accuracy on all three benchmarks. AQuA SVAMP MMLU Ablation Δ . Δ Δ . Δ Δ . Δ 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 4.3 RQ2: LAWA as a Plug-in Module We further evaluate LAWA as a plug-in structural optimizer by applying it to workflows generated by different baseline methods, without modifying their original generation procedures. Specifically, we extract the workflow graphs produced by each baseline and use each graph as the initialization for LAWA. To mitigate randomness, each baseline is executed three times, and we report the average changes in performance and makespan before and after applying LAWA. As shown in Table 3, LAWA consistently reduces the makespan of workflows produced by all baseline methods while showing no systematic degradation in mean task performance in the reported settings. This suggests that the proposed graph modification operators can compress makespan with limited impact on downstream accuracy. Notably, these gains are observed across diverse initial topologies, including both chain-structured and general DAG workflows. This indicates that LAWA’s optimization behavior does not rely on chain-structured initialization. Overall, the results demonstrate that LAWA can serve as a flexible plug-in module for latency-aware workflow optimization. 4.4 RQ3: Robustness under Inaccurate or Perturbed Evaluator Decisions To evaluate robustness under an imperfect evaluator, we flip the evaluator’s keep/reject decision with probability α at the filtering step in Algorithm 1 (line 12) for each candidate graph during optimization and report final task performance under small perturbation rates α∈0.0,0.1,0.2α∈\0.0,0.1,0.2\. As shown in Table 4, LAWA remains stable under mild evaluator perturbations, with performance close to the unperturbed setting for α≤0.2α≤ 0.2. These results suggest that occasional evaluator mistakes have limited impact on final performance under mild perturbations. 4.5 RQ4: Component Ablations To isolate the sources of LAWA’s latency and performance gains, we ablate the two graph-editing operations and the two training stages of the Graph Generator, and report the resulting changes relative to full LAWA in Table 5. Removing either Node Removal or Parallel Rewiring restricts the optimizer to a single type of edit; the resulting optimization terminates earlier and yields longer makespans. Both ablations also reduce accuracy on all three benchmarks, as the available structures are more limited. For Graph Generator training, removing either SFT or DPO reduces accuracy on all three benchmarks, with consistently larger degradation without DPO. Both training stages therefore contribute to performance, with DPO having the larger effect. 5 Related Works Workflow Generation for LLM-MAS. Empowered by Large Language Models, LLM-based multi-agent systems leverage multiple specialized agents and structured coordination to solve complex tasks across domains Yang et al. (2023); Li et al. (2023); Hong et al. (2024). Early systems often rely on manually specified protocols, static interaction topologies, or SOP-style workflows Wu et al. (2024); Qian et al. (2024); Zhang et al. (2024). To reduce manual design effort, recent work explores automated workflow generation and orchestration, including LLM-generated or modular workflow synthesis Zhang et al. (2025d); Xu et al. (2025); Niu et al. (2025), parallel or broadcast-style collaboration Liu et al. (2024); Zhang et al. (2025a), routing-based agent selection Yang et al. (2025c); Yang et al. (2025b); Yue et al. (2025), and graph-based topology learning or pruning Zhang et al. (2025b); Wang et al. (2025b); Zhang et al. (2025c); Li et al. (2025). Despite these advances, most methods primarily optimize task performance, communication efficiency, or token cost, rather than explicitly minimizing workflow makespan. Makespan Optimization for LLM-MAS. Latency is an increasingly important bottleneck for LLM-MAS, since multi-step agent workflows introduce repeated LLM calls, synchronization barriers, and service-side congestion Chen et al. (2025a); Zhang et al. (2025a). Existing latency-oriented studies mainly address the LLM serving layer Chen et al. (2025a); Shen et al. (2026); Dai et al. (2025); Ni et al. (2026); Agarwal et al. (2026); Kang et al. (2026), while optimization of the workflow topology itself remains relatively underexplored. Recent topology learning methods such as LAMaS Shi et al. (2026) and AgentBalance Cai et al. (2025) begin to incorporate latency into MAS topology design; however, LAMaS focuses on predefined layer-wise parallel orchestration, while AgentBalance mainly treats latency as a budget constraint without a theoretical analysis of topology-level makespan reduction. LAWA fills this gap by optimizing arbitrary DAG-structured LLM-MAS workflows and providing theoretical characterizations of graph edits in terms of reachability preservation, non-increasing makespan, and expressivity. 6 Conclusion In this paper, we present LAWA, a latency-aware framework for optimizing Large Language Model-based multi-agent workflows. LAWA uses makespan-guided graph editing to shorten critical paths, while a learned evaluator guides the search toward workflows that preserve downstream task performance. Across seven benchmarks, LAWA produces lower-latency execution graphs and can also serve as a plug-in optimizer for existing workflows. We hope this work encourages further study of workflow-level latency optimization in multi-agent systems. Additional discussion of limitations is provided in Appendix G. References [1] T. L. Adam, K. M. Chandy, and J. Dickson (1974) A comparison of list schedules for parallel processing systems. Communications of the ACM 17 (12), p. 685–690. Cited by: §F.4. [2] S. Agarwal, M. Laju, D. Son, N. Kedia, M. Lee, J. Srinivasa, and A. Akella (2026) Nalar: workflow-aware management of agentic applications. arXiv preprint arXiv:2601.05109. Cited by: §5. [3] J. Austin, A. Odena, M. Nye, et al. (2021) Program synthesis with large language models. arXiv preprint arXiv:2108.07732. Cited by: §4.1. [4] S. Cai, Y. Ning, and H. Liu (2025) AgentBalance: backbone-then-topology design for cost-effective multi-agent systems under budget constraints. arXiv preprint arXiv:2512.11426. Cited by: §5. [5] J. Chen, J. Shi, Q. Chen, and M. Guo (2025) Kairos: low-latency multi-agent serving with shared llms and excessive loads in the public cloud. arXiv preprint arXiv:2508.06948. Cited by: §1, §5. [6] M. Chen et al. (2021) Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. Cited by: §4.1. [7] Y. Chen, M. Shetty, G. Somashekar, M. Ma, Y. Simmhan, J. Mace, C. Bansal, R. Wang, and S. Rajmohan (2025) AIOpsLab: a holistic framework to evaluate ai agents for enabling autonomous clouds. arXiv preprint arXiv:2501.06706. External Links: 2501.06706, Link Cited by: §1. [8] K. Cobbe, V. Kosaraju, M. Bavarian, et al. (2021) Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: §4.1. [9] Y. Dai, Z. Chen, A. Iyer, and R. Netravali (2025) Aragog: just-in-time model routing for scalable serving of agentic workflows. arXiv preprint arXiv:2511.20975. External Links: 2511.20975, Link Cited by: §5. [10] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt (2021) Measuring massive multitask language understanding. Proceedings of the International Conference on Learning Representations (ICLR). Cited by: §4.1. [11] D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt (2021) Measuring mathematical problem solving with the math dataset. NeurIPS. Cited by: §4.1. [12] S. Hong, M. Zhuge, J. Chen, et al. (2024) MetaGPT: meta programming for a multi-agent collaborative framework. In The twelfth international conference on learning representations, Cited by: §1, §1, §5. [13] A. B. Kahn (1962) Topological sorting of large networks. Commun. ACM 5 (11), p. 558–562. External Links: ISSN 0001-0782, Link, Document Cited by: §A.3. [14] H. Kang, Z. Li, X. Yang, W. Xu, Y. Chen, J. Wang, B. Chen, T. Krishna, C. Xu, and S. Arora (2026) ThunderAgent: a simple, fast and program-aware agentic inference system. arXiv preprint arXiv:2602.13692. Cited by: §5. [15] G. Li, H. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem (2023) Camel: communicative agents for" mind" exploration of large language model society. Advances in Neural Information Processing Systems 36, p. 51991–52008. Cited by: §5. [16] S. Li, Y. Liu, Q. Wen, C. Zhang, and S. Pan (2025) Assemble your crew: automatic multi-agent communication topology design via autoregressive graph generation. arXiv preprint arXiv:2507.18224. Cited by: §1, §5. [17] W. Ling, D. Yogatama, C. Dyer, and P. Blunsom (2017) Program induction by rationale generation : learning to solve and explain algebraic word problems. arXiv preprint arXiv:1705.04146. External Links: 1705.04146, Link Cited by: §4.1. [18] Z. Liu, Y. Zhang, P. Li, Y. Liu, and D. Yang (2024) A dynamic LLM-powered agent network for task-oriented agent collaboration. In First Conference on Language Modeling, Cited by: §4.1, §5. [19] K. Ni, W. Hua, X. Shi, J. Guo, S. Chang, and T. Chen (2026) Chimera: latency-and performance-aware multi-agent serving for heterogeneous llms. arXiv preprint arXiv:2603.22206. Cited by: §5. [20] B. Niu, Y. Song, K. Lian, Y. Shen, Y. Yao, K. Zhang, and T. Liu (2025) Flow: modularized agentic workflow automation. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §5. [21] A. Patel, S. Bhattamishra, and N. Goyal (2021) Are nlp models really able to solve simple math word problems?. arXiv preprint arXiv:2103.07191. External Links: 2103.07191, Link Cited by: §4.1. [22] C. Qian, W. Liu, H. Liu, et al. (2024) Chatdev: communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 15174–15186. Cited by: §5. [23] R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn (2023) Direct preference optimization: your language model is secretly a reward model. Advances in neural information processing systems 36, p. 53728–53741. Cited by: §3.5. [24] J. Shen, N. Wadlom, and Y. Lu (2026) Batch query processing and optimization for agentic workflows. arXiv preprint arXiv:2509.02121. External Links: 2509.02121, Link Cited by: §5. [25] X. Shi, M. Zheng, and Q. Lou (2026) Learning latency-aware orchestration for parallel multi-agent systems. arXiv preprint arXiv:2601.10560. Cited by: §4.1, §5. [26] H. Wang, X. Peng, H. Cheng, Y. Huang, M. Gong, C. Yang, Y. Liu, and J. Lin (2025) ECom-bench: can LLM agent resolve real-world E-commerce customer support issues?. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing: Industry Track, S. Potdar, L. Rojas-Barahona, and S. Montella (Eds.), Suzhou (China), p. 276–284. External Links: Link, Document, ISBN 979-8-89176-333-3 Cited by: §1. [27] Z. Wang, Y. Wang, X. Liu, L. Ding, M. Zhang, J. Liu, and M. Zhang (2025) AgentDropout: dynamic agent elimination for token-efficient and high-performance llm-based multi-agent collaboration. arXiv preprint arXiv:2503.18891. Cited by: §4.1, §5. [28] Q. Wu, G. Bansal, J. Zhang, et al. (2024) Autogen: enabling next-gen llm applications via multi-agent conversations. In First Conference on Language Modeling, Cited by: §5. [29] S. Xu, J. Zhang, S. Di, Y. Luo, L. Yao, H. Liu, J. Zhu, F. Liu, and M. Zhang (2025) RobustFlow: towards robust agentic workflow generation. arXiv preprint arXiv:2509.21834. External Links: 2509.21834, Link Cited by: §5. [30] A. Yang, A. Li, B. Yang, et al. (2025) Qwen3 technical report. arXiv preprint arXiv:2505.09388. External Links: 2505.09388, Link Cited by: §4.1. [31] H. Yang, S. Yue, and Y. He (2023) Auto-gpt for online decision making: benchmarks and additional opinions. arXiv preprint arXiv:2306.02224. External Links: 2306.02224, Link Cited by: §1, §5. [32] Q. Yang, F. Qu, T. Guo, Y. Liu, and Y. Wen (2025) Augmented runtime collaboration for self-organizing multi-agent systems: a hybrid bi-criteria routing approach. arXiv preprint arXiv:2512.00740. External Links: 2512.00740, Link Cited by: §4.1, §5. [33] Y. Yang, H. Chai, S. Shao, Y. Song, S. Qi, and W. Zhang (2025) AgentNet: decentralized evolutionary coordination for llm-based multi-agent systems. arXiv preprint arXiv:2504.00587. Cited by: §5. [34] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, M. Boyer, and T. Liu (2021) Do transformers really perform badly for graph representation?. Advances in Neural Information Processing Systems 34, p. 28877–28888. Cited by: §F.7. [35] Y. Yue, G. Zhang, B. Liu, G. Wan, K. Wang, D. Cheng, and Y. Qi (2025) MasRouter: learning to route llms for multi-agent systems. arXiv preprint arXiv:2502.11133. Cited by: §5. [36] C. Zhang, K. Yang, S. Hu, et al. (2024) Proagent: building proactive cooperative agents with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 17591–17599. Cited by: §5. [37] E. Zhang, E. Zhu, G. Bansal, A. Fourney, H. Mozannar, and J. Gerrits (2025) Optimizing sequential multi-step tasks with parallel llm agents. arXiv preprint arXiv:2507.08944. External Links: 2507.08944, Link Cited by: §1, §5, §5. [38] G. Zhang, Y. Yue, Z. Li, S. Yun, G. Wan, K. Wang, D. Cheng, J. X. Yu, and T. Chen (2025) Cut the crap: an economical communication pipeline for llm-based multi-agent systems. ICLR. Cited by: §4.1, §5. [39] G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, and D. Cheng (2025) G-designer: architecting multi-agent communication topologies via graph neural networks. arXiv preprint arXiv:2410.11782. Cited by: §4.1, §5. [40] J. Zhang, J. Xiang, Z. Yu, et al. (2025) AFlow: automating agentic workflow generation. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §1, §4.1, §5. Appendix A Proofs of Theoretical Properties Here we provide formal proofs for the properties in the main text. A.1 Proof of Theorem 3.4 Proof. We analyze the two operations separately: 1. Node Removal (of k): Let k∈∖vI,vOk \v_I,v_O\ and ′=∖kV =V \k\. We consider any u,v∈′u,v . (⟹)( ) Forward Direction: Assume u↝Gvu _Gv. Let P be a path from u to v in G. • If k∉Pk∉ P, then P consists entirely of nodes in ′V and edges unchanged by the operation. Thus, P exists in G′G . • If k∈Pk∈ P, the path contains a segment x→k→yx→ k→ y. The removal operation explicitly adds the shortcut edge x→yx→ y to G′G whenever x→kx→ k and k→yk→ y exist in G. We can replace every occurrence of x→k→yx→ k→ y with the single edge x→yx→ y, yielding a valid path in G′G . (⟸)( ) Reverse Direction: Assume u↝G′vu _G v. Let P′P be a path in G′G . Edges in G′G are either original edges from G or newly created shortcut edges. • If an edge (x,y)∈P′(x,y)∈ P exists in G, it represents the direct connection x→yx→ y. • If an edge (x,y)∈P′(x,y)∈ P is a new shortcut not in G, it implies that x was a predecessor of k and y was a successor of k in G. Thus, this edge corresponds to the path segment x→k→yx→ k→ y in G. 2. Parallel Rewiring (of edge i→ji→ j): We consider u,v∈∖i,ju,v \i,j\. Note that the operation removes i→ji→ j and updates connectivity such that j inherits i’s predecessors (incoming merge) and i inherits j’s successors (outgoing merge). (⟹)( ) Forward Direction: Assume u↝Gvu _Gv. Let P be a path in G. • If (i,j)∉P(i,j)∉ P, the path from u to v remains intact in G′G since only edge i→ji→ j is removed. • If (i,j)∈P(i,j)∈ P, the path from u to v contains a segment x→i→j→yx→ i→ j→ y. In G′G , the operation sets xj′←1A _xj← 1 (since x→ix→ i) and iy′←1A _iy← 1 (since j→yj→ y). We can bypass the removed edge by using the new edge x→jx→ j, creating a path ...→x→j→y→…...→ x→ j→ y→... in G′G . (⟸)( ) Reverse Direction: Assume u↝G′vu _G v. Let P′P be a path in G′G . Any edge in P′P is either an original edge or a newly formed edge due to merging neighborhoods. • A new edge of type x→jx→ j exists in G′G only if x→ix→ i existed in G. Thus, x→jx→ j in P′P corresponds to the segment x→i→jx→ i→ j in G. • A new edge of type i→yi→ y exists in G′G only if j→yj→ y existed in G. Thus, i→yi→ y in P′P corresponds to the segment i→j→yi→ j→ y in G. Since u,v≠i,ju,v≠ i,j, the path must start and end outside the rewired edge. By expanding any new edges back to their original segments involving i→ji→ j, we recover a valid path in G. ∎ A.2 Proof of Theorem 3.5 Proof. Let G(vI,vO)P_G(v_I,v_O) denote the set of all directed execution paths from the entry node vIv_I to the exit node vOv_O in graph G. It suffices to show that for every path P′∈G′(vI,vO)P _G (v_I,v_O) in the edited graph, there exists a corresponding path P∈G(vI,vO)P _G(v_I,v_O) in the original graph such that ∑v∈P′tv≤∑v∈Ptv. _v∈ P t_v\;≤\; _v∈ Pt_v. (i) Node Removal. Suppose a non-terminal node k∈∖vI,vOk \v_I,v_O\ is removed. For any path P′∈G′(vI,vO)P _G (v_I,v_O): • If P′P uses only original edges from G, then the same path exists in G, and the path duration is identical. • If P′P uses a shortcut edge (u,v)(u,v) introduced by removing k, then G contains the segment u→k→vu→ k→ v. Replacing every such shortcut in P′P by its original two-edge segment yields a valid path P in G, with ∑v∈P′tv≤∑v∈Ptv, _v∈ P t_v≤ _v∈ Pt_v, since tk>0t_k>0. (i) Parallel Rewiring. Suppose the edge (i,j)(i,j) is rewired. For any path P′∈G′(vI,vO)P _G (v_I,v_O): • If P′P uses only original edges from G, then the same path exists in G. • Otherwise, every edge newly introduced by the rewiring is either of the form x→jx→ j where x→ix→ i existed in G, or of the form i→yi→ y where j→yj→ y existed in G. We can replace each new edge x→jx→ j by the segment x→i→jx→ i→ j, and each new edge i→yi→ y by the segment i→j→yi→ j→ y. This recovers a valid path P in G and only inserts nodes with positive latency. Hence ∑v∈P′tv≤∑v∈Ptv. _v∈ P t_v≤ _v∈ Pt_v. Thus, every execution path in G′G is no longer than a corresponding path in G. Taking the maximum over paths in G′G yields T(G′)=max∑v∈P′P′∈G′(vI,vO)tv≤max∑v∈P∈G(vI,vO)tv=T(G). T(G )= _P _G (v_I,v_O) _v∈ P t_v≤ _P _G(v_I,v_O) _v∈ Pt_v=T(G). ∎ A.3 Proof of Theorem 3.6 Proof. The transformation from an arbitrary chain to the target graph G∗G is achieved via a three-stage procedure. We prove the validity of each stage sequentially. Stage 1: Topological Alignment (via Permutation). Let σ:→σ:V be a permutation such that applying the operator Πσ _σ to the initial chain yields a sequence where, for every directed edge (u,v)(u,v) in G∗G , node u precedes v. This condition ensures that the linear ordering defined by the permuted chain is consistent with the topological sort of G∗G [13]. Stage 2: Node Alignment (via Removal). If the initial chain contains nodes not required by G∗G , we apply Node Removal to eliminate all extraneous nodes. By reachability preservation, removing nodes does not alter the relative reachability among the remaining nodes. After this stage, the graph is a chain defined exactly on the target node set V, with an ordering consistent with G∗G . Therefore, the permuted chain after the node permutation is the topological sort of G∗G . Without loss of generality, we assign node indices according to this ordered chain, starting from v1v_1 to vnv_n. Stage 3: Exact Edge Reconstruction (via Rewiring) With the nodes correctly aligned and ordered, we employ a Reverse Sweeping strategy to recover the exact edge structure. We first define the construction, then prove its correctness. I. The Construction. We execute the following iterative procedure to refine the graph structure: For each node viv_i iterating from vn−1v_n-1 down to v1v_1 (reverse from end to start): • Let out′(vi)N_out (v_i) denote the current set of immediate successors of viv_i. • While there exists a neighbor vk∈out′(vi)v_k _out (v_i) such that (vi,vk)(v_i,v_k) not in G∗G : – Do: Apply Parallel Rewiring to the edge (vi,vk)(v_i,v_k), which updates: out′(vi)←(out′(vi)∖vk)∪out′(vk)N_out (v_i)←(N_out (v_i) \v_k\) _out (v_k) • End While (All remaining immediate successors are now valid target neighbors). End For I. Correctness Verification. We prove that this process yields G′≅G∗G G using structural induction on the node index i (descending from n to 11). Inductive Hypothesis: Assume that for all nodes vjv_j in the downstream of viv_i (j>ij>i), the outgoing edges are already identical to the target graph: out′(vj)=out∗(vj)N_out (v_j)=N_out (v_j). (Base case vnv_n is trivial). Inductive Step: Consider node viv_i. We verify the final state of out′(vi)N_out (v_i) when the rewiring loop for viv_i terminates. 1. No False Positives: The loop condition explicitly mandates the removal of any edge (vi,vk)(v_i,v_k) that does not exist in G∗G . Thus, out′(vi)⊆out∗(vi)N_out (v_i) _out (v_i). 2. No False Negatives: Consider any valid target neighbor vm∈out∗(vi)v_m _out (v_i). For the sake of contradiction, suppose that vmv_m is absent from the current immediate successor set out′(vi)N_out (v_i). • Since no Parallel Rewiring operation has been applied to (vi,vm)(v_i,v_m), the reachability is strictly preserved (Theorem 3.4), the absence of a direct link implies that vmv_m must be reachable via some intermediate neighbor vk∈out′(vi)v_k _out (v_i). • Because the loop has terminated, vkv_k is confirmed to be a valid target neighbor (i.e., (vi,vk)(v_i,v_k) exists in G∗G ). • Furthermore, since k>ik>i, the inductive hypothesis guarantees that the path segment vk→…→vmv_k→…→ v_m exists in G∗G . • Consequently, G∗G contains both the direct edge (vi,vm)(v_i,v_m) and the indirect path vi→vk→…→vmv_i→ v_k→…→ v_m. This structure violates the transitive reduction property of G∗G . • Thus, the assumption is false. No such blocking node vkv_k can exist, and vmv_m must be present in out′(vi)N_out (v_i). Thus, out′(vi)=out∗(vi)N_out (v_i)=N_out (v_i). By induction, after the loop terminates at v1v_1, the graph G′G is exactly isomorphic to G∗G . ∎ Appendix B Derivation of the Parallel Rewiring Score Let ∈0,1n×nA∈\0,1\^n× n denote the adjacency matrix of the workflow graph, and let =∂Sθ∂∈ℝn×n = ∂ S_θ ^n× n be the gradient of the Graph Evaluator score SθS_θ with respect to A. For a graph edit that induces a perturbation Δ , a first–order Taylor expansion yields ΔS≈⟨,Δ⟩=∑u,vuvΔuv. S\;≈\; , \;=\; _u,v _uv\, _uv. (16) Rewiring an edge (i,j)(i,j) removes the original edge i→ji\!→\!j and merges the outgoing neighbors of j into i, as well as the incoming neighbors of i into j. Accordingly, the perturbation Δ consists of three parts: • Removal of the edge (i,j)(i,j), giving Δij=−ij _ij=-A_ij; • Addition of edges (i,k)(i,k) for all k such that jk=1A_jk=1 and ik=0A_ik=0; • Addition of edges (k,j)(k,j) for all k such that ki=1A_ki=1 and kj=0A_kj=0. Substituting these changes into (16) gives ΔS(i,j)≈ S(i,j)\;≈\; −ijij - _ijA_ij +∑kikjk(1−ik) + _k _ik\,A_jk(1-A_ik) +∑kjki(1−kj), + _k _kj\,A_ki(1-A_kj), (17) which is the stated first–order estimate of the score change induced by rewiring (i,j)(i,j). For compactness, define =⊙H= and ~=⊙(1−) H= (1-A). The three terms in (17) can then be written in matrix form, yielding the parallel–rewiring score matrix rwr=−+~⊤+⊤~, ^rwr\;=\;-\,H\;+\; H\,A \;+\;A H, (18) where each entry i,jrwrR^rwr_i,j equals ΔS(i,j) S(i,j) and provides the first–order estimated score change for rewiring edge (i,j)(i,j). Appendix C Details in Experiment Settings Agent Settings. We define specific agent pools for each domain to support specialized reasoning. For the Code Generation domain (MBPP, HumanEval), the available agents include: AlgoPlanner, CodeGenerator, CodeAuditor, ConceptualAlgorithmist, LegacyPythonCoder, ComplianceChecker, Generalists and STEM_Expert. For the Mathematical Reasoning domain (GSM8K, MATH500, SVAMP, AQuA), the candidate agents are: MathReasoner, Calculator, STEM_Expert, ProblemSimplifier, HeuristicMathSolver, Generalists, ConsensusBuilder, ExecutiveArbitrator, ContrarianThinker, Verifier, and LateralThinkingAnalyst. For the General Knowledge domain (MMLU), the agent pool consists of: LateralThinkingAnalyst, SocialScientist, Generalists, STEM_Expert, MathReasoner, TheoreticalScientist, CriticalTheorist, HeuristicMathSolver, ContrarianThinker, and ConsensusBuilder. Serving Environment. For wall-clock makespan measurements, each run uses a freshly launched and warmed-up SGLang server on an NVIDIA RTX PRO 6000 Blackwell Max-Q Workstation Edition GPU (96GB memory), with exclusive GPU allocation during measurement. Graph Dataset Construction. To train the Graph Evaluator and the Graph Generator for each task, we construct benchmark-specific graph datasets. For each benchmark, we generate a fixed pool of N=2048N=2048 random graphs using the agent candidates from the corresponding task domain. To obtain the ground-truth performance labels (scores) for each graph G, we evaluate G on a subset of task samples from that benchmark’s training set. Specifically, we use k=50k=50 samples for mathematical reasoning datasets (GSM8K, MATH500, SVAMP, AQuA) and k=30k=30 samples for code generation (HumanEval, MBPP) and general knowledge (MMLU) datasets. Since HumanEval and MATH500 do not provide official training splits, we use equivalent training proxies: for HumanEval, we build HumanEval-compatible training samples from the MBPP train split; for MATH500, we sample from the MATH train split (levels 4–5) while excluding instances that overlap with the MATH500 test set. The average accuracy across these k samples serves as the target label for training. We also use the same samples for the training-based baselines. LAWA Parameters. For the optimization phases, we use fixed beam size of B=32B=32. The maximum number of optimization steps (iterations) is set to K=11K=11 for the generation experiments and K=4K=4 for the plugin-experiments due to reduced workflow depth. Our implementation and scripts for reproducing the experiments are available at https://github.com/GraphmindDartmouth/LAWA. Appendix D Case Study: Optimization Trajectory on MBPP. To illustrate the step-by-step optimization behavior of LAWA, we start from a chain-structured workflow on MBPP and apply LAWA with beam size B=1B=1, so that it will only modify the single best candidate graph of the last iteration. Figure 3 illustrates the optimization trajectory. The original workflow achieves an accuracy of 63.9% and exhibits a fully sequential dependency pattern, resulting in a long critical path. In the first step, LAWA applies parallel rewiring between Generalists and AlgoPlanner, exposing latent parallelism without altering the agent set. This change shortens the critical path and yields a slight accuracy improvement to 64.1%. In the second step, LAWA removes the second ComplianceChecker node. This node contributes redundant computation along the critical path, and its removal further reduces the makespan while increasing accuracy to 65.6%. In the third step, LAWA performs parallel rewiring between ComplianceChecker and CodeAuditor. While this modification slightly reduces accuracy to 65.2%, it eliminates a remaining sequential dependency and reduces the runtime contribution of ComplianceChecker. Among these steps, LAWA incrementally compresses the critical path while maintaining stable task performance. 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. Appendix E Probabilistic Robustness Analysis under Evaluator Perturbations We provide a probabilistic justification for the robustness behavior observed in RQ3 under evaluator perturbations. Let ℳM denote the set of valid candidate graphs generated during optimization, where each G∈ℳG satisfies the true constraint S(G)≥S(G0)S(G)≥ S(G_0), and let U denote the set of invalid candidates with S(G)<S(G0)S(G)<S(G_0). Define the top-tier valid set as ℳ∗=v∈ℳ∣T(v)<minu∈T(u),M =\v T(v)< _u T(u)\, which contains valid candidates whose makespan is smaller than any invalid candidate. The optimization procedure outputs G∗=argminG∈T(G),G = _G T(G), where =G∈ℳ∪∣Sθ(G)≥Sθ(G0)W=\G S_θ(G)≥ S_θ(G_0)\ is the retained set under the Graph Evaluator. Assume an otherwise accurate evaluator whose keep/reject decision at Algorithm 1 (line 12) is independently perturbed (flipped) with probability α. Then two events must simultaneously happen for an invalid final output: (i) at least one invalid candidate is falsely kept, and (i) all top-tier valid candidates are falsely rejected. Conditioned on (,ℳ∗)(U,M ), we have Pr(G∗∈∣,ℳ∗) (G ,M ) ≤Pr(∃u∈,u∈)⋅Pr(∀v∈ℳ∗,v∉) ≤ (∃ u ,\,u )· (∀ v ,\,v ) =(1−(1−α)||)α|ℳ∗| = (1-(1-α)^|U| )α^|M | ≤(1−(1−α)N¯)α|ℳ∗|, ≤ (1-(1-α) N )α^|M |, (19) where N¯ N is an upper bound on the number of candidates. Let p0=Pr(|ℳ∗|=0)p_0= (|M |=0). Marginalizing over candidate sets yields Pr(G∗∈) (G ) =∑,ℳ∗Pr(G∗∈∣,ℳ∗)Pr(,ℳ∗) = _U,M (G ,M ) (U,M ) ≤(1−(1−α)N¯)∑ℳ∗α|ℳ∗|Pr(ℳ∗) ≤ (1-(1-α) N ) _M α^|M | (M ) =(1−(1−α)N¯)(∑k=0∞Pr(|ℳ∗|=k)αk) = (1-(1-α) N ) ( _k=0^∞ (|M |=k)α^k ) ≤(1−(1−α)N¯)(p0+(1−p0)α). ≤ (1-(1-α) N ) (p_0+(1-p_0)α ). (20) Therefore, the probability of an invalid final output is explicitly determined by α. As α→0α→ 0, the upper bound also approaches 00, consistent with RQ3, where performance remains stable under mild perturbations. Table 6: Behavior of LAWA under limited executors. Here m 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 × 3 runs). m Runtime Improvement (%) Operation Counts (rewire/remove) 1 43.67 19/64 2 65.38 83/61 3 67.74 91/59 4 67.89 92/59 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±std_ [rgb]0.3,0.3,0.3 ) over 3 runs. Results show that the approximation does not introduce a noticeable drop in accuracy. Setting MATH500 HumanEval AQuA w/o approximation 67.00±0.7167.00_ [rgb]0.3,0.3,0.3± 0.71 93.29±0.0093.29_ [rgb]0.3,0.3,0.3± 0.00 83.86±0.5683.86_ [rgb]0.3,0.3,0.3± 0.56 w/ approximation 67.00±0.8667.00_ [rgb]0.3,0.3,0.3± 0.86 92.89±1.0492.89_ [rgb]0.3,0.3,0.3± 1.04 83.46±0.8583.46_ [rgb]0.3,0.3,0.3± 0.85 Appendix F More Experiment Results F.1 Token Consumption To examine whether parallel rewiring increases context-broadcasting overhead, we report total token consumption (input + output) of the generated workflows for all methods under the same final setting. As shown in Table 8, LAWA consistently remains token-efficient. The token consumption is substantially lower than heavily parallel baselines such as DyLAN. This is because total token usage is largely determined by the number of agent invocations, and LAWA removes redundant nodes during optimization. Table 8: Total token consumption per query (Tokens↓ ) on seven benchmarks. We report total token consumption (input + output) for all methods. Values are mean±std_ [rgb]0.3,0.3,0.3 over three runs, and the best value in each benchmark is bolded. Method MBPP HumanEval AQuA GSM8K MATH500 SVAMP MMLU Rand. Graph 22768±194922768_ [rgb]0.3,0.3,0.3± 1949 34403±432634403_ [rgb]0.3,0.3,0.3± 4326 64483±235064483_ [rgb]0.3,0.3,0.3± 2350 40409±868540409_ [rgb]0.3,0.3,0.3± 8685 57252±801857252_ [rgb]0.3,0.3,0.3± 8018 40825±168440825_ [rgb]0.3,0.3,0.3± 1684 48050±620448050_ [rgb]0.3,0.3,0.3± 6204 Rand. Chain 40289±422940289_ [rgb]0.3,0.3,0.3± 4229 49315±363849315_ [rgb]0.3,0.3,0.3± 3638 99064±1175399064_ [rgb]0.3,0.3,0.3± 11753 83317±44683317_ [rgb]0.3,0.3,0.3± 446 103547±5895103547_ [rgb]0.3,0.3,0.3± 5895 71156±123571156_ [rgb]0.3,0.3,0.3± 1235 73758±82173758_ [rgb]0.3,0.3,0.3± 821 3-Round Disc. 219103±7310219103_ [rgb]0.3,0.3,0.3± 7310 243745±3320243745_ [rgb]0.3,0.3,0.3± 3320 595536±12769595536_ [rgb]0.3,0.3,0.3± 12769 500286±2419500286_ [rgb]0.3,0.3,0.3± 2419 646475±21625646475_ [rgb]0.3,0.3,0.3± 21625 445061±7785445061_ [rgb]0.3,0.3,0.3± 7785 470002±1510470002_ [rgb]0.3,0.3,0.3± 1510 DyLAN 55388±392155388_ [rgb]0.3,0.3,0.3± 3921 72015±550072015_ [rgb]0.3,0.3,0.3± 5500 85396±933085396_ [rgb]0.3,0.3,0.3± 9330 41915±2063841915_ [rgb]0.3,0.3,0.3± 20638 98495±377798495_ [rgb]0.3,0.3,0.3± 3777 62078±255362078_ [rgb]0.3,0.3,0.3± 2553 81276±130181276_ [rgb]0.3,0.3,0.3± 1301 G-Designer 37128±255037128_ [rgb]0.3,0.3,0.3± 2550 44954±115744954_ [rgb]0.3,0.3,0.3± 1157 88371±412488371_ [rgb]0.3,0.3,0.3± 4124 80719±334780719_ [rgb]0.3,0.3,0.3± 3347 99698±455699698_ [rgb]0.3,0.3,0.3± 4556 70241±508970241_ [rgb]0.3,0.3,0.3± 5089 67340±296067340_ [rgb]0.3,0.3,0.3± 2960 AgentDropout 19870±930719870_ [rgb]0.3,0.3,0.3± 9307 27288±1027827288_ [rgb]0.3,0.3,0.3± 10278 54616±532854616_ [rgb]0.3,0.3,0.3± 5328 29668±733429668_ [rgb]0.3,0.3,0.3± 7334 46292±796646292_ [rgb]0.3,0.3,0.3± 7966 41654±401141654_ [rgb]0.3,0.3,0.3± 4011 46553±1092046553_ [rgb]0.3,0.3,0.3± 10920 AgentPrune 34834±578834834_ [rgb]0.3,0.3,0.3± 5788 46360±22246360_ [rgb]0.3,0.3,0.3± 222 88365±334388365_ [rgb]0.3,0.3,0.3± 3343 75535±107975535_ [rgb]0.3,0.3,0.3± 1079 99848±399599848_ [rgb]0.3,0.3,0.3± 3995 59406±528059406_ [rgb]0.3,0.3,0.3± 5280 62790±532462790_ [rgb]0.3,0.3,0.3± 5324 BiRouter 11338±278911338_ [rgb]0.3,0.3,0.3± 2789 16150±388616150_ [rgb]0.3,0.3,0.3± 3886 14843±363914843_ [rgb]0.3,0.3,0.3± 3639 9344±9299344_ [rgb]0.3,0.3,0.3± 929 15100±351415100_ [rgb]0.3,0.3,0.3± 3514 8448±2278448_ [rgb]0.3,0.3,0.3± 227 14763±366614763_ [rgb]0.3,0.3,0.3± 3666 AFlow 11865±303711865_ [rgb]0.3,0.3,0.3± 3037 16532±382516532_ [rgb]0.3,0.3,0.3± 3825 35135±417235135_ [rgb]0.3,0.3,0.3± 4172 23594±212023594_ [rgb]0.3,0.3,0.3± 2120 35469±482835469_ [rgb]0.3,0.3,0.3± 4828 22166±267522166_ [rgb]0.3,0.3,0.3± 2675 24833±457824833_ [rgb]0.3,0.3,0.3± 4578 LAMaS 7898±1507898_ [rgb]0.3,0.3,0.3± 150 11705±24011705_ [rgb]0.3,0.3,0.3± 240 14047±397614047_ [rgb]0.3,0.3,0.3± 3976 15841±653315841_ [rgb]0.3,0.3,0.3± 6533 17849±254417849_ [rgb]0.3,0.3,0.3± 2544 13766±207013766_ [rgb]0.3,0.3,0.3± 2070 15012±10315012_ [rgb]0.3,0.3,0.3± 103 LAWA 6516±306516_ [rgb]0.3,0.3,0.3± 30 11401±409911401_ [rgb]0.3,0.3,0.3± 4099 10796±412110796_ [rgb]0.3,0.3,0.3± 4121 10461±186210461_ [rgb]0.3,0.3,0.3± 1862 12207±315212207_ [rgb]0.3,0.3,0.3± 3152 7615±23047615_ [rgb]0.3,0.3,0.3± 2304 15077±289715077_ [rgb]0.3,0.3,0.3± 2897 F.2 Optimization Runtime To better characterize computational overhead of LAWA, we report both (i) wall-clock time to generate one workflow and (i) Graph Evaluator training time. Unless otherwise stated, runtime measurements in this section are conducted on a machine with an AMD EPYC 9655 96-Core Processor CPU. As shown in Table 9, workflow generation typically takes only around 1–2.3 seconds because the search operates only on graph structure without executing real agent calls. Compared with high-latency baseline workflows in Table 1, this search overhead is small relative to recurrent execution costs. As shown in Table 10, Graph Evaluator training takes 21–95 seconds per benchmark and is performed once per benchmark as an offline preprocessing step. Therefore, when LAWA is used repeatedly to replace high-latency workflows, this one-time overhead can be easily amortized over subsequent executions. For example, using Random Chain as a representative high-latency initial workflow, the one-time evaluator-training and search cost is offset after roughly 2–7 recurrent executions across benchmarks. Cost of graph-dataset construction. On MATH500, constructing the full graph dataset (evaluating 2048 randomly generated workflows on 50 training samples) takes 38.7 minutes of wall-clock time on 8 NVIDIA RTX PRO 6000 GPUs. This is a one-time, fully parallelizable offline stage: unlike on-policy baselines, whose data collection is sequential and repeated during optimization, LAWA’s workflow evaluations have no sequential dependency. On the same server, the complete LAWA pipeline (dataset generation, training, and workflow generation) takes 41.2 minutes, whereas AgentDropout requires 129.6 minutes under the same 2048-rollout budget (64 iterations × batch size 32). The gap arises because evaluating 2048 workflows in one pass fully utilizes the inference server: it costs only about 20×20× the time of evaluating 32 workflows, despite processing 64×64× as many workflows. Thus, even after including graph-dataset construction, LAWA takes about one third of the wall-clock time of this on-policy baseline. Table 9: Wall-clock time to generate a single workflow (Seconds↓ ). Benchmark Time (s) MBPP 2.2736±0.22872.2736_ [rgb]0.3,0.3,0.3± 0.2287 HumanEval 1.1563±0.40621.1563_ [rgb]0.3,0.3,0.3± 0.4062 AQuA 1.6917±0.76761.6917_ [rgb]0.3,0.3,0.3± 0.7676 GSM8K 2.2471±0.16132.2471_ [rgb]0.3,0.3,0.3± 0.1613 MATH500 1.7981±0.14301.7981_ [rgb]0.3,0.3,0.3± 0.1430 SVAMP 2.2039±0.27682.2039_ [rgb]0.3,0.3,0.3± 0.2768 MMLU 2.1496±0.18322.1496_ [rgb]0.3,0.3,0.3± 0.1832 Table 10: Wall-clock time to train the Graph Evaluator (Seconds↓ ). Benchmark Train Time (s) MBPP 44.45 HumanEval 21.32 AQuA 63.34 GSM8K 34.65 MATH500 46.47 SVAMP 23.32 MMLU 95.08 F.3 Frontier Backbone Model We additionally evaluate the officially hosted frontier model Kimi-K2.6 on MBPP, MATH500, and MMLU, comparing LAWA with DyLAN and AgentDropout. For LAWA, we reuse the original Graph Evaluator, Graph Generator, and estimated tkt_k values, without retraining the learned modules or recalibrating the latency estimates. As shown in Table 11, LAWA’s performance advantage is preserved with the stronger backbone: it remains best on MBPP and MMLU, and is on par with DyLAN on MATH500. A stronger backbone makes each individual agent more capable, so a compact workflow can attain high accuracy with fewer agents, which favors LAWA’s ability to remove redundant agents. LAWA also remains the fastest method on all three benchmarks. Table 11: Accuracy (%↑ ) and real wall-clock makespan (s↓ ) with Kimi-K2.6. Values are mean±std_ [rgb]0.3,0.3,0.3 over three workflow graphs. MBPP MATH500 MMLU Method Acc. Time Acc. Time Acc. Time DyLAN 73.41±0.2273.41_ [rgb]0.3,0.3,0.3± 0.22 40.27±5.9240.27_ [rgb]0.3,0.3,0.3± 5.92 81.20±1.2581.20_ [rgb]0.3,0.3,0.3± 1.25 32.01±9.5332.01_ [rgb]0.3,0.3,0.3± 9.53 80.73±1.8080.73_ [rgb]0.3,0.3,0.3± 1.80 33.07±1.0333.07_ [rgb]0.3,0.3,0.3± 1.03 AgentDropout 72.24±0.5972.24_ [rgb]0.3,0.3,0.3± 0.59 43.66±2.3743.66_ [rgb]0.3,0.3,0.3± 2.37 79.27±2.8979.27_ [rgb]0.3,0.3,0.3± 2.89 43.34±1.9843.34_ [rgb]0.3,0.3,0.3± 1.98 79.82±3.6179.82_ [rgb]0.3,0.3,0.3± 3.61 52.66±13.1552.66_ [rgb]0.3,0.3,0.3± 13.15 LAWA 73.80±0.8173.80_ [rgb]0.3,0.3,0.3± 0.81 14.19±1.2114.19_ [rgb]0.3,0.3,0.3± 1.21 81.27±1.2281.27_ [rgb]0.3,0.3,0.3± 1.22 18.43±2.9918.43_ [rgb]0.3,0.3,0.3± 2.99 81.74±1.7781.74_ [rgb]0.3,0.3,0.3± 1.77 19.75±2.1019.75_ [rgb]0.3,0.3,0.3± 2.10 F.4 Finite-Resource Scheduling We study how LAWA’s editing policy changes when the available parallel resources are constrained. During graph editing, we replace the default critical-path estimator (Equation 1) with an HLFET list-scheduling runtime estimator [1] and vary the number of executors m∈1,2,3,4m∈\1,2,3,4\. Runtime improvement is measured as the relative reduction against the initial workflow, and operation counts are aggregated over all generated instances (7 benchmarks × 3 runs). As reported in Table 6, the optimization behavior shows a clear transition: under single-executor constraints, LAWA mainly shortens the critical chain through node removal, while with more executors it increasingly prefers rewiring to unlock parallel branches; correspondingly, runtime gains improve quickly at first and then gradually plateau as available parallelism approaches saturation. This indicates that, even under limited executors, LAWA can adapt its editing strategy to the available resources. F.5 Robustness under First-Order Approximation We examine whether the first-order gradient approximation used to filter rewiring operations harms final optimization quality. We compare default LAWA (with approximation) against a variant that disables approximation and computes rewiring-score changes exactly during candidate generation, then evaluate final accuracy on MATH500, HumanEval, and AQuA. As shown in Table 7, the performance differences are minor across benchmarks, indicating that the approximation does not introduce a noticeable drop in final accuracy while helping reduce the number of candidate graphs. F.6 Effectiveness of the Graph Evaluator We conduct an ablation study to examine whether the Graph Evaluator stabilizes LAWA’s iterative graph editing process. Starting from the same randomly initialized chain workflows, we compare the default LAWA against a variant without evaluator-based filtering, which keeps candidates only according to makespan. Table 12 reports the downstream-performance change across optimization steps on two representative benchmarks. With the Graph Evaluator, LAWA yields positive mean performance changes across optimization steps, whereas removing the evaluator leads to less stable performance and can result in degradation. These results suggest that the Graph Evaluator helps retain downstream task quality while the structural optimizer reduces latency. Table 12: Performance change across optimization steps with and without the Graph Evaluator. Values are downstream-performance changes (%, mean±std_ [rgb]0.3,0.3,0.3 ) relative to the initial workflow, computed over eight different random initial graphs. Dataset Method Step 1 Step 2 Step 3 Step 4 Step 5 HumanEval LAWA (w/ Evaluator) +1.68±1.99+1.68_ [rgb]0.3,0.3,0.3± 1.99 +2.21±2.97+2.21_ [rgb]0.3,0.3,0.3± 2.97 +2.29±3.22+2.29_ [rgb]0.3,0.3,0.3± 3.22 +2.44±3.37+2.44_ [rgb]0.3,0.3,0.3± 3.37 +1.75±2.54+1.75_ [rgb]0.3,0.3,0.3± 2.54 HumanEval w/o Evaluator −0.30±2.14-0.30_ [rgb]0.3,0.3,0.3± 2.14 −0.15±2.82-0.15_ [rgb]0.3,0.3,0.3± 2.82 −0.07±2.26-0.07_ [rgb]0.3,0.3,0.3± 2.26 −0.53±2.12-0.53_ [rgb]0.3,0.3,0.3± 2.12 −2.74±1.72-2.74_ [rgb]0.3,0.3,0.3± 1.72 MATH500 LAWA (w/ Evaluator) +0.95±0.60+0.95_ [rgb]0.3,0.3,0.3± 0.60 +1.65±1.09+1.65_ [rgb]0.3,0.3,0.3± 1.09 +1.25±1.17+1.25_ [rgb]0.3,0.3,0.3± 1.17 +1.65±1.14+1.65_ [rgb]0.3,0.3,0.3± 1.14 +1.35±1.23+1.35_ [rgb]0.3,0.3,0.3± 1.23 MATH500 w/o Evaluator −0.20±0.63-0.20_ [rgb]0.3,0.3,0.3± 0.63 −0.35±1.19-0.35_ [rgb]0.3,0.3,0.3± 1.19 −0.45±1.19-0.45_ [rgb]0.3,0.3,0.3± 1.19 −0.63±1.34-0.63_ [rgb]0.3,0.3,0.3± 1.34 −1.72±1.51-1.72_ [rgb]0.3,0.3,0.3± 1.51 F.7 Graph Evaluator Architecture Sensitivity We evaluate how sensitive the Graph Evaluator is to GNN architecture choices and justify the default backbone used in LAWA. On HumanEval, we run a full ablation over GNN type (gcn, gat, transformer), depth (1–4 layers), and hidden size (256/512), while keeping all other training settings fixed and reporting train/test accuracy over 3 seeds. Table 13 indicates that GCN performs most consistently across configurations, while the performance of GAT and Transformer varies more with depth and hidden size. The 3-layer Transformer with hidden dimension 512 achieves both train and test accuracy above 95%, and Graph Transformers are generally more suited to capture the long-range interactions that may arise from multi-hop dependencies in workflow graphs [34]. Therefore, we use a 3-layer Transformer with hidden dimension 512 as the default Graph Evaluator. Appendix G Limitations and Future Works This work considers a static agent pool and a fixed set of downstream tasks, a standard setting that is widely adopted in prior work. In practice, agent availability and task distributions may evolve over time. Extending the framework to more dynamic scenarios is a promising direction for future work. In dynamic environments, the set of available agents may change over time, leading to changes in the feasible workflows and the associated makespan. Extending the framework to accommodate a dynamic agent pool would require the workflow to adapt to such changes while maintaining efficiency. Similarly, downstream tasks may evolve over time, potentially altering the desirable workflow patterns. Developing mechanisms that allow the evaluator and workflow to adapt to such shifts in a data-efficient and incremental manner, rather than being rebuilt from scratch, is another important direction for future work. 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±std_ [rgb]0.3,0.3,0.3 ) over 3 seeds. Rows where both train and test mean exceed 95 are bolded. Hidden Dim GNN Type #Layers Train Acc (%) Test Acc (%) 256 gcn 1 94.68±0.6894.68_ [rgb]0.3,0.3,0.3± 0.68 94.79±3.3594.79_ [rgb]0.3,0.3,0.3± 3.35 256 gcn 2 94.63±0.4994.63_ [rgb]0.3,0.3,0.3± 0.49 95.17±4.2895.17_ [rgb]0.3,0.3,0.3± 4.28 256 gcn 3 95.05±0.4495.05_ [rgb]0.3,0.3,0.3± 0.44 95.14±2.5895.14_ [rgb]0.3,0.3,0.3± 2.58 256 gcn 4 94.93±0.2094.93_ [rgb]0.3,0.3,0.3± 0.20 95.77±3.3095.77_ [rgb]0.3,0.3,0.3± 3.30 256 gat 1 94.97±0.7394.97_ [rgb]0.3,0.3,0.3± 0.73 94.47±3.2794.47_ [rgb]0.3,0.3,0.3± 3.27 256 gat 2 95.38±1.2795.38_ [rgb]0.3,0.3,0.3± 1.27 94.00±3.7494.00_ [rgb]0.3,0.3,0.3± 3.74 256 gat 3 94.22±1.6394.22_ [rgb]0.3,0.3,0.3± 1.63 93.57±3.7493.57_ [rgb]0.3,0.3,0.3± 3.74 256 gat 4 95.00±0.7795.00_ [rgb]0.3,0.3,0.3± 0.77 92.44±3.8792.44_ [rgb]0.3,0.3,0.3± 3.87 256 transformer 1 94.18±0.5894.18_ [rgb]0.3,0.3,0.3± 0.58 93.47±4.3693.47_ [rgb]0.3,0.3,0.3± 4.36 256 transformer 2 95.35±1.4795.35_ [rgb]0.3,0.3,0.3± 1.47 94.43±4.3594.43_ [rgb]0.3,0.3,0.3± 4.35 256 transformer 3 94.75±1.7094.75_ [rgb]0.3,0.3,0.3± 1.70 94.03±4.1494.03_ [rgb]0.3,0.3,0.3± 4.14 256 transformer 4 93.60±1.5893.60_ [rgb]0.3,0.3,0.3± 1.58 94.00±2.9094.00_ [rgb]0.3,0.3,0.3± 2.90 512 gcn 1 94.92±1.3994.92_ [rgb]0.3,0.3,0.3± 1.39 95.11±3.8095.11_ [rgb]0.3,0.3,0.3± 3.80 512 gcn 2 95.43±0.6895.43_ [rgb]0.3,0.3,0.3± 0.68 95.45±2.9495.45_ [rgb]0.3,0.3,0.3± 2.94 512 gcn 3 95.07±0.8095.07_ [rgb]0.3,0.3,0.3± 0.80 94.17±4.0394.17_ [rgb]0.3,0.3,0.3± 4.03 512 gcn 4 94.85±0.5894.85_ [rgb]0.3,0.3,0.3± 0.58 95.28±1.9595.28_ [rgb]0.3,0.3,0.3± 1.95 512 gat 1 95.00±1.5495.00_ [rgb]0.3,0.3,0.3± 1.54 94.90±2.2194.90_ [rgb]0.3,0.3,0.3± 2.21 512 gat 2 95.13±1.1695.13_ [rgb]0.3,0.3,0.3± 1.16 93.40±4.3593.40_ [rgb]0.3,0.3,0.3± 4.35 512 gat 3 95.13±1.0995.13_ [rgb]0.3,0.3,0.3± 1.09 93.82±2.1693.82_ [rgb]0.3,0.3,0.3± 2.16 512 gat 4 95.70±0.8295.70_ [rgb]0.3,0.3,0.3± 0.82 93.25±3.8993.25_ [rgb]0.3,0.3,0.3± 3.89 512 transformer 1 93.12±1.4593.12_ [rgb]0.3,0.3,0.3± 1.45 91.67±2.6491.67_ [rgb]0.3,0.3,0.3± 2.64 512 transformer 2 93.23±0.3593.23_ [rgb]0.3,0.3,0.3± 0.35 89.93±6.8689.93_ [rgb]0.3,0.3,0.3± 6.86 512 transformer 3 95.97±1.2995.97_ [rgb]0.3,0.3,0.3± 1.29 95.11±4.3995.11_ [rgb]0.3,0.3,0.3± 4.39 512 transformer 4 95.28±3.6895.28_ [rgb]0.3,0.3,0.3± 3.68 94.68±4.0694.68_ [rgb]0.3,0.3,0.3± 4.06