Benchmarking Agentic Workflow Generation¶

🕒 Published (v1): 2025-01-01 · Source: ICLR · Venue: ICLR 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

WorfBench is a benchmark for evaluating LLM agents on graph-structured workflow generation across four task domains, paired with WorFEval, an evaluation protocol based on subsequence and subgraph matching. Comprehensive evaluation of 18 models reveals a consistent and significant gap between linear (chain) planning and graph (DAG) planning capabilities, with even GPT-4 achieving only 52.47% on graph-structured workflows.

Problem¶

Existing workflow generation benchmarks are limited to linear (sequential) subtask decomposition, narrow scenario coverage (mostly function-calling or reasoning), and imprecise evaluation that relies on GPT-based judges or simple string matching. None properly assess an agent's ability to generate DAG-structured workflows with parallel execution paths, which is necessary for real-world task decomposition.

Method¶

Benchmark construction (WorfBench): Tasks are collected from ToolBench, ALFWorld, WebShop, LUMOS, and WikiHow, spanning four scenarios (function call, embodied planning, problem-solving, open-grounded). Workflows are represented as DAGs $G(V, E)$ where nodes are minimum-granularity subtasks and edges encode execution dependencies. Generation follows a two-step pipeline: first produce a node chain $C(V)$ (a topological sequence), then infer edges to build $G(V, E)$. GPT-4 synthesizes both chains and graphs; quality is enforced by (1) retrieval-based node alignment filtering (15.36% discarded) and (2) topological sort consistency checks (29.77% discarded).

Evaluation (WorFEval): Nodes are matched via cosine similarity (Sentence-BERT, threshold $\beta=0.6$) with max-weighted bipartite matching to produce one-to-one node correspondences $V^{g'} \leftrightarrow V^{p'}$. Chain quality uses Longest Increasing Subsequence (LIS) matching over topological orders, yielding $f1^{\text{chain}}$. Graph quality uses Maximum Common Induced Subgraph (MCIS) matching, yielding: $$f1^{\text{graph}} = \frac{2 p^{\text{graph}} r^{\text{graph}}}{p^{\text{graph}} + r^{\text{graph}}}, \quad p^{\text{graph}} = \frac{k}{|V^p|}, \quad r^{\text{graph}} = \frac{k}{|V^g|}$$ where $k = |V_{\text{mcis}}|$ is the size of the maximum common induced subgraph.

Key Contributions¶

WorfBench: 18k training / 2146 test / 723 held-out samples across four scenario types with DAG-structured gold workflows and strict quality control.
WorFEval: Algorithm-based evaluation using LIS (chain) and MCIS (graph) matching, avoiding LLM-judge hallucination and ambiguity.
Systematic evaluation of 18 LLMs (7B–72B open-source + GPT-3.5/4, O1, Claude-3.5), revealing a universal chain→graph performance gap.
Fine-tuned open-source models (Qwen-2-7B+FT, InternLM-2.5-7B+FT) showing strong held-in performance with evaluated generalization on held-out tasks.
Downstream utility analysis: generated workflows improve inference efficiency as CoT augmentation by enabling parallel subtask execution.

Results¶

GPT-4: avg $f1^{\text{chain}}=67.32\%$, $f1^{\text{graph}}=52.47\%$ — a ~15% chain-to-graph gap.
All 18 models show a chain-to-graph gap; largest is GLM-4-9B at 20.05%; smallest is Llama-3.1-70B at 15.01%.
Best closed-source on average: GPT-4 ($f1^{\text{chain}}=67.32\%$, $f1^{\text{graph}}=52.47\%$); Claude-3.5 leads on open-grounded graph ($f1^{\text{graph}}=42.88\%$).
Best open-source on average: Qwen-2-72B ($f1^{\text{chain}}=67.24\%$, $f1^{\text{graph}}=50.46\%$).
Open-grounded tasks are hardest: top performer (Claude-3.5) scores only $f1^{\text{graph}}=42.88\%$.
Fine-tuned Qwen-2-7B+FT: $f1^{\text{chain}}=79.35\%$, $f1^{\text{graph}}=70.38\%$ on held-in tasks; generalization to held-out Seal-Tools: 82.82% graph, but drops to 48.72% on InterCodeSQL.
Scaling law holds within series (Qwen-2 72B beats 7B by 6.77% in $f1^{\text{graph}}$; Llama-3.1 70B beats 8B by 11.51%), but recent 7B models outperform older 13B models.
O1 excels on problem-solving tasks but underperforms on other scenarios requiring environmental knowledge.

Limitations¶

Gold workflow graphs are synthesized by GPT-4, introducing potential systematic biases from the generator into the benchmark ground truth.
MCIS matching is NP-hard; the paper caps topological order enumeration at 20, which may introduce approximation error on large graphs.
Performance degrades with increasing node/edge count (shown for GPT-4), but the benchmark does not stress-test very large workflows.
Held-out generalization of fine-tuned models is inconsistent (strong on Seal-Tools, weaker on InterCodeSQL), suggesting limited cross-domain transfer.
Evaluation is structure-only; semantic correctness of subtask decomposition beyond node matching is not captured.

Relevance to Harnesses / Meta-Harnesses¶

WorfBench directly measures the core capability that meta-harnesses rely on: decomposing a complex task description into a structured, executable workflow DAG. The chain→graph performance gap quantifies precisely how much current LLMs struggle with the parallel-branch dependency structures that sophisticated harnesses (e.g., pipeline/fan-out orchestrators) require agents to plan correctly. The WorFEval metrics ($f1^{\text{chain}}$, $f1^{\text{graph}}$) offer a rigorous evaluation protocol reusable by anyone building harnesses that delegate workflow planning to an LLM backbone. The finding that generated workflows can reduce downstream inference time via parallelism is directly actionable for harness designers choosing between sequential and parallel agent orchestration.