GPBench: Benchmarking LLMs for Orchestrating Multi-stage Graph Analysis Workflow

Real-world graph analysis often requires composing multiple graph algorithms into a workflow, where graph data are processed through dependent stages to solve a single analytical problem. Manually constructing such workflows requires substantial expertise in graph algorithms and their execution dependencies. Large language models (LLMs) provide a promising approach to automating this process by translating high-level user requests into graph-analysis workflows. However, doing so requires LLMs to jointly decompose an analytical problem into concrete operations, select an appropriate algorithm for each operation, and resolve algorithm parameters and cross-stage dependencies, making workflow orchestration substantially more challenging than conventional graph-analysis tasks evaluated for LLMs.Existing benchmarks primarily focus on general planning, single-step tool use, or graph problems with a single computational objective, leaving multi-stage graph-analysis workflow orchestration insufficiently evaluated. We present GPBench, a benchmark evaluating three core capabilities: workflow decomposition, algorithm selection, and dependency and parameter resolution. GPBench contains 1,000 multi-stage graph-analysis problems across five representative workflow topologies. Experiments show that Graph Planner achieves 82.7% accuracy on workflow decomposition. A hierarchical graph-algorithm knowledge base improves strict Top-1 algorithm-selection accuracy from 71.7% to 82.9%, while models achieve up to 90.0% workflow-instantiation accuracy given the correct algorithms and their parameter descriptions. However, end-to-end composition causes substantial performance degradation due to error propagation across stages, indicating that improving individual stages alone is insufficient. We further introduce targeted improvements to the major error-prone components to improve end-to-end workflow orchestration. Code and data are available at https://anonymous.4open.science/r/GPBench-F305/.