acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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/.

Primary area:
datasets and benchmarks
Keywords:
Large Language Models, Graph Analysis, Multi-stage Graph Analytics, Graph Algorithm

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_31npOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

GPBench contains 1,000 graph-analysis problems for evaluating workflow decomposition, algorithm selection, and parameter and dependency resolution. The authors provide execution-validated reference workflows and evaluate domain-guided prompting and hierarchical algorithm retrieval, both independently and in a three-stage pipeline.

Critical strengths

The execution-validated reference workflows and separate evaluation of decomposition, algorithm selection, and parameter binding provide a useful resource for diagnosing errors in graph-tool orchestration.

Critical weaknesses

The writing and figures need substantial improvement. Many sentences have a formulaic, AI-like style that makes the paper unnecessarily difficult to read. Several figures, particularly Figure 2, also give the impression of rough AI-generated drafts rather than carefully prepared scientific illustrations. My concern is not AI use itself, but the insufficient editing and visual polish.

The benchmark largely asks models to recover a workflow already described in the question, rather than determine how to solve a high-level analytical problem. Questions are generated from preselected workflows while preserving their operations, parameters, and dependencies, even when algorithm names are omitted. This makes the task closer to semantic parsing and algorithm identification. The benchmark may be useful for that narrower purpose, but its value as an evaluation of autonomous graph-analysis planning is insufficiently established.

Questions for authors

What substantive planning decisions remain open to the model once the question specifies the required operations and dependencies? How does GPBench distinguish planning ability from recovering an already-described workflow?

2 comments
AuthorsOpenReview ↗

Responses to Reviewer 31np (1/2)

W1. Improving the writing and figures

Thank you for pointing out these issues with the writing and figures. We have edited the experimental discussion to reduce repetitive, overly general, and formulaic phrasing. Based on the additional model comparisons and specific errors observed in the experiments, we have revised the analyses of task decomposition, algorithm selection, and parameter binding, and added an analysis of the end-to-end experimental results. We have also revised the relevant figures, with particular attention to Figure 2, to improve their clarity and visual presentation.

AuthorsOpenReview ↗

Responses to Reviewer 31np (2/2)

Q1 / W2. What decisions does the model need to make?

In GPBench, planning is required throughout graph analysis, including problem decomposition, algorithm selection, and dependency binding.

Even when a question specifies the analytical requirements, operations, and relationships between stages, the model must still map these requirements to concrete graph operations, select algorithms based on graph properties and downstream needs, and determine how intermediate results are used in subsequent computations. For example, the model must decide whether an upstream node set should be used to construct the input subgraph for a downstream algorithm or bound to its source-node parameter. Our end-to-end experiments further evaluated these decisions and their implementation: as shown in Table 1, with IRA enabled, GPT-5.5 achieved a workflow accuracy of 53.10% and a final-answer accuracy of 45.10%. We also observed that some generated programs mishandled intermediate results passed between stages.

Table 1. Workflow and final-answer accuracy of our three-stage pipeline on the dataset.

ModelWorkflow Accuracy (w/o IRA)Workflow Accuracy (w/ IRA)Final-answer Accuracy (w/o IRA)Final-answer Accuracy (w/ IRA)
Qwen3-8B6.50%7.00%2.60%2.70%
Qwen3.8-Flash (Non-Thinking)41.90%44.30%35.20%36.80%
Qwen3.8-Flash (Thinking)47.90%48.10%39.40%39.50%
DeepSeek-V4-Flash46.90%52.20%39.40%41.80%
GPT-5.548.80%53.10%42.40%45.10%
Reviewer_PqSDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

GPBench introduces a benchmark that tests whether LLMs can translate graph-analysis requests written in natural language into executable workflows composed of multiple graph algorithms. It evaluates three levels: workflow decomposition, algorithm selection, and parameter and data-dependency resolution. The authors construct a dataset of 1,000 problems and propose two prompting- and retrieval-based methods, Graph Planner and Hierarchical RAG, to improve performance on the individual subtasks. The main evaluated models are GPT-5.5 and DeepSeek-V4-Flash. The results show that although models perform well on the individual tasks, end-to-end workflow accuracy remains low (48.8% exact match). Reliably turning natural-language requests into complete, executable multi-stage graph-analysis workflows therefore remains a challenge for current LLMs.

Critical strengths

S1. The problem setting and evaluation framework are well motivated. Existing graph benchmarks mostly test single-algorithm problems, whereas this paper focuses on composing multiple graph algorithms into a workflow. It evaluates three stages separately (task decomposition, algorithm selection, and parameter/dependency resolution), making it possible to identify the stage at which errors occur. This setting is closer to real-world graph analysis needs, and the stage-wise diagnosis is useful for guiding future improvements.

S2. The data are reliable. Every problem has an execution-validated Python reference program, the LLM-based evaluator for Task 1 is validated against human judgments (Appendix B.1.3), and an anonymous link to the code and data is provided. These reliable and reproducible annotations give the benchmark practical value as an evaluation resource.

Critical weaknesses

W1. The set of evaluated models is limited: only two general-purpose LLMs (GPT-5.5 and DeepSeek-V4-Flash) are evaluated. G1-CoT-SFT-7B appears only in Task 2, and its prompt omits graph attributes (Appendix B.2 and D.9), putting it at a disadvantage. The end-to-end evaluation uses only a single pipeline with GPT-5.5. Open-source models of different sizes are missing, and there is no comparison between reasoning and non-reasoning models. As a result, the conclusions about current LLMs' capabilities on this task have limited generalizability.

W2. All problems are generated by having an LLM verbalize sampled algorithm chains, with only 2–5 stages and 5 topologies, making the problems relatively templated. In addition, 540 problems (54%) have only 2–3 stages, while only 100 have 5 stages (Table 2). The existing analyses (error-type statistics in Figure 4 and dependency diagnostics in Figure 5) are mainly descriptive. They do not investigate in depth why models fail or which capabilities determine success, so the conclusions offer limited guidance for future work.

Questions for authors
  1. Could you add results for more models, including open-source models of different sizes and reasoning models, and report their end-to-end performance?

  2. Beyond the error-type statistics in Figure 4 (Task 1) and the dependency diagnostics in Figure 5 (Task 3), the paper lacks an analysis of why models fail. Could you provide deeper error analyses, especially for Task 2 and the end-to-end evaluation, that explain the underlying causes of failure?

3 comments
AuthorsOpenReview ↗

Responses to Reviewer PqSD(1/3)

W1 / Q1. Model coverage and end-to-end performance

Thank you for your suggestion. We added the open-weight model Qwen3-8B and the Thinking and Non-Thinking modes of Qwen3.8-Flash, expanding our evaluation to five backend configurations, including GPT-5.5 and DeepSeek-V4-Flash. We conducted task-level evaluations for the three newly added configurations and end-to-end evaluations for all five configurations on 1,000 synthetic questions, including executing the generated workflows on the corresponding graphs. The additional results show that Graph Planner and Hierarchical RAG maintain their accuracy advantages across the newly added configurations. For Qwen3.8-Flash with IRA, enabling Thinking mode improves final-answer accuracy from 36.80% to 39.50%. Detailed results are presented below.

Task 1: Problem-to-Workflow Decomposition

The additional experiments further validate the effectiveness of Graph Planner in problem decomposition. It achieves the highest node, edge, and workflow accuracy across all three additional Qwen configurations, with absolute workflow accuracy gains of 3.50%–9.70% over the strongest generic baseline in each configuration (Table R1). Graph Planner uses graph-analysis operations as planning units: computational objectives determine subtask content, while expected outputs define subtask boundaries and dependencies. These explicit planning criteria help accurately identify the required operations and their connections, thereby improving problem-to-workflow decomposition.

Table R1. Problem-to-workflow decomposition for the three additional Qwen configurations. Accuracy values are percentages.

LLM BackendMethodNode Acc.Edge Acc.Workflow Acc.Tokens
Qwen3-8BLLM-CoT29.0040.0027.004,592.68
LLM-ToT60.0067.0054.006,601.14
LLM-GoT53.0058.0050.006,175.31
Graph Planner63.5074.0057.5010,527.00
Qwen3.8-Flash (Non-Thinking)LLM-CoT65.0094.5063.501,599.12
LLM-ToT80.5092.0076.503,770.12
LLM-GoT36.5036.0034.002316.49
Graph Planner84.1096.5082.502,673.21
Qwen3.8-Flash (Thinking)LLM-CoT56.0091.5055.005,045.23
LLM-ToT74.5090.0069.0011,152.74
LLM-GoT79.0090.0071.509,173.80
Graph Planner83.8094.0081.204,876.43

Task 2: Subtask-to-Algorithm Matching

The additional experiments show that Hierarchical RAG achieves more accurate algorithm matching with lower token usage. Given the reference subtasks, it achieves higher question-level Top-1 accuracy across all three additional Qwen configurations than Flat KB, which selects directly from the full algorithm library, with absolute accuracy gains of 16.00%–16.50% (Table R2). Hierarchical retrieval first narrows the candidate set by task category, then uses within-category semantic relations to distinguish similar algorithms, helping reduce irrelevant information and improve selection accuracy. We also added the missing graph attributes to the G1-CoT-SFT-7B prompt and reevaluated the model.

Table R2. Subtask-to-algorithm matching for the three additional Qwen configurations and G1-CoT-SFT-7B with the corrected prompt. Accuracy values are percentages.

LLM BackendMethodkCategory Acc.Subtask Acc.Overall Acc.Tokens
Qwen3.8-Flash (Non-Thinking)Flat KB1--82.3255.50100,627.60
3--91.5279.00100,963.40
5--93.3085.00117,190.09
Hierarchical RAG195.6090.3071.5026,147.40
395.9094.0581.5026,484.40
596.1094.9485.5028,682.69
Qwen3.8-Flash (Thinking)Flat KB1--83.8758.50102,035.80
3--93.7279.50112,328.00
5--97.1790.50140,013.29
Hierarchical RAG196.8091.2874.5031,191.80
396.8097.2093.5041,871.40
597.1098.9696.7042,034.70
Qwen3-8BFlat KB1--0.60.30110,627.60
3--1.521.30119,963.40
5--2.561.90120,190.09
Hierarchical RAG164.7051.5216.8035,503.76
370.4065.4227.1038,667.83
570.6065.4530.3044,998.54
G1-CoT-SFT-7BDirect Prediction1--35.595.004,380.56
3--48.8413.805,235.95
5--61.0121.406,027.67
AuthorsOpenReview ↗

Responses to Reviewer PqSD(2/3)

W1 / Q1. Model coverage and end-to-end performance (continued)

Task 3: Parameter and Dependency Resolution

Given the reference DAG, algorithms, and parameter and output specifications, Qwen3-8B resolves all parameters and bindings on 26.50% of questions (Table R3). On Qwen3.8-Flash, enabling thinking raises overall accuracy from 73.50% to 84.20%. Dynamic binding accuracy rises from 82.00% to 93.00%, while static parameter accuracy changes from 88.50% to 90.50%.

Table R3. Parameter and dependency resolution for the three additional Qwen configurations, with GraphForge as a baseline. Accuracy values are percentages. Bold marks the highest displayed accuracies and the lowest token count.

LLM BackendStatic Acc.Dynamic Acc.Overall Acc.Tokens
GraphForge50.1043.3022.602,808.64
Qwen3-8B53.0049.0026.502,887.08
Qwen3.8-Flash (Non-Thinking)88.5082.0073.502,833.61
Qwen3.8-Flash (Thinking)90.5093.0084.204733.13

End-to-End Performance under Five Backend Configurations

We further evaluated the workflows generated by the complete three-stage pipeline and executed them on the corresponding input graphs to verify the correctness of the final answers. Table R4 reports the workflow accuracy and final-answer accuracy of the five configurations, with and without intermediate result alignment (IRA).

Table R4. Workflow and final-answer accuracy of our three-stage pipeline on the 1,000 synthetic problems.

ModelWorkflow Accuracy w/o IRAWorkflow Accuracy w/ IRAFinal-answer Accuracy w/o IRAFinal-answer Accuracy w/ IRA
Qwen3-8B6.50%7.00%2.60%2.70%
Qwen3.8-Flash (Non-Thinking)41.90%44.30%35.20%36.80%
Qwen3.8-Flash (Thinking)47.90%48.10%39.40%39.50%
DeepSeek-V4-Flash46.90%52.20%39.40%41.80%
GPT-5.548.80%53.10%42.40%45.10%

W2 / Q2. Workflow diversity and why models fail

Thank you for asking which decisions cause a workflow to fail. We examined the predicted operations and edges, audited algorithm choices against the requested computations, and traced how intermediate results were assigned to downstream arguments.

Task 1. Error Analysis

Thank you for this comment. Our further analysis of Task 1 shows that models struggle to determine what each operation produces directly and what additional processing is needed. As shown in Figure 4, with Graph Planner, missing operations and incorrect output types together still account for 75.59% and 74.24% of the error labels for GPT-5.5 and DeepSeek-V4-Flash, respectively. When we inspected the predicted workflows, we found cases where the model treated the result of a later processing step as the direct output of the current operation. For example, a question may require finding nodes within two hops of a given node using breadth-first search, filtering them by degree, and constructing a subgraph. If the model lists the subgraph as the direct output of the search, it omits the filtering step and mislabels the node set as a subgraph.

Task 2. Error Analysis

We found that a key difficulty in Task 2 is extracting specific computational requirements from a high-level analytical goal and using them to distinguish between algorithms with similar purposes. Of GPT-5.5's 151 substantive algorithm selection errors, 81.46% involved computational rules, applicability conditions, or required outputs. For example, a model may recognize that a question asks for link prediction based on common neighbors and still miss the specified weighting rule. The resource allocation index and the Adamic–Adar index both use common neighbors to score candidate links, but they weight those neighbors differently. Selecting an algorithm based only on its broad purpose can therefore produce scores under a different rule from the one requested. In the ablation study in Table 5, removing semantic relations between algorithms in the same category reduced question-level Top-1 accuracy from 82.90% to 77.00% for GPT-5.5 and from 78.90% to 72.70% for DeepSeek-V4-Flash.

AuthorsOpenReview ↗

Responses to Reviewer PqSD(3/3)

W2 / Q2. Workflow diversity and why models fail (continued)

Task 3. Error Analysis

We found that the key difficulty in Task 3 is determining from the question what role each intermediate result plays in the downstream computation. Even when the workflow structure, algorithms, and their parameter and output specifications are given, a model may identify the correct upstream step and still pass its result to the wrong parameter. Figure 5(a) shows that accuracy for GraphForge, DeepSeek-V4-Flash, and GPT-5.5 is lower when both the upstream step and the receiving parameter must be correct than when only the upstream step is checked. Figure 5(b) also shows that DeepSeek-V4-Flash and GPT-5.5 are less accurate on data dependencies than on graph dependencies. A graph dependency typically identifies which graph the next algorithm takes as input, whereas data dependencies may involve several results of the same type. For example, the source and target parameters of a path query both accept node identifiers. Swapping the two identifiers preserves the expected parameter types but reverses the direction of the query.

End-to-End Failure Analysis

We found that algorithm selection accounts for the largest drop after decomposition. Some workflows that pass the planning checks still yield incorrect answers because the generated code processes or uses intermediate results incorrectly. Table 8 shows that GPT-5.5 passed the decomposition check on 827 of the 1,000 questions. Of these, 601 also passed the strict algorithm selection check, a drop of 226 questions at this step. After checking parameters and dependencies, 488 questions passed all planning checks. Once the analytical steps are identified, the model still needs to choose algorithms that perform the required computations and determine which downstream parameter should receive each intermediate result. With IRA enabled, GPT-5.5 achieved 53.10% workflow accuracy and 45.10% final-answer accuracy. The corresponding results for DeepSeek-V4-Flash were 52.20% and 41.80%. For example, one question asks the model to compute the harmonic centrality h(v)h(v) of each node, update each edge weight to the mean of its endpoints' scores, w′(u,v)=[h(u)+h(v)]/2w'(u,v)=[h(u)+h(v)]/2, and compute a minimum spanning tree using the new weights. If the code computes the centrality scores but still uses the original weights to find the tree, it can run successfully and return a tree that minimizes the sum of the original edge weights. Diagnosing this error requires checking which weights the spanning tree algorithm actually uses.

W2. Workflow Diversity and Design Rationale.

Thank you for your suggestion. The five topologies and the range of 2–5 stages constrain the overall logical structure of workflows, while the specific algorithms, output requirements, inter-stage data dependencies, and uses of intermediate results depend on the analysis objective. For example, two tasks may share the same two-stage sequential topology: one converts upstream node scores into edge weights, while the other uses these scores to select nodes and construct a subgraph for downstream analysis. These differences entail different data transformations, parameter bindings, and graph scopes, so the same structure can correspond to different computational tasks. The selected dependency patterns and algorithm combinations also have practical grounding. Montage and CyberShake include pipelines, data distribution, and data aggregation [1]; Vertexica uses local clustering coefficients to select the source node for single-source shortest paths [2], while GraphScope combines PageRank and neighborhood sampling in its recommendation pipeline [3]. In future work, we will introduce longer workflows and multiple levels of branching and merging to broaden structural coverage.

References for the workflow examples.

[1] Bharathi, S., Chervenak, A., Deelman, E., Mehta, G., Su, M.-H., and Vahi, K. "Characterization of Scientific Workflows." 2008 Third Workshop on Workflows in Support of Large-Scale Science (WORKS), 1–10, 2008. https://doi.org/10.1109/WORKS.2008.4723958

[2] Jindal, A., Rawlani, P., Wu, E., Madden, S., Deshpande, A., and Stonebraker, M. "Vertexica: Your Relational Friend for Graph Analytics!" Proceedings of the VLDB Endowment, 7(13), 1669–1672, 2014. https://www.vldb.org/pvldb/vol7/p1669-jindal.pdf

[3] Fan, W., He, T., Lai, L., Li, X., Li, Y., Li, Z., Qian, Z., Tian, C., Wang, L., Xu, J., Yao, Y., Yin, Q., Yu, W., Zhou, J., Zhu, D., and Zhu, R. "GraphScope: A Unified Engine For Big Graph Processing." Proceedings of the VLDB Endowment, 14(12), 2879–2892, 2021. https://doi.org/10.14778/3476311.3476369

Reviewer_Xv1JOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

GPBench evaluates whether LLMs can translate a high-level natural-language graph-analysis question into an executable multi-stage graph-algorithm workflow. It decomposes orchestration into three diagnosable capabilities—workflow decomposition, subtask-to-algorithm selection, and cross-stage dependency and parameter resolution—and supplies a substantial set of execution-validated multi-stage problems spanning representative workflow topologies. The benchmark is grounded in a hierarchical knowledge base that organizes graph algorithms by task category, specification, and semantic relations, enabling both reference construction and fine-grained error localization. The authors also propose targeted methods for the major error sources: structured planning guidance, hierarchical retrieval for algorithm selection, and intermediate-result alignment across stages. The central finding is one of mismatch: models perform reasonably well when each stage is evaluated in isolation, yet end-to-end composition degrades sharply due to error propagation and semantic mismatches between stages. This shows that reliable workflow orchestration cannot be achieved by improving individual components alone.

Critical strengths
  • GPBench addresses a genuine gap: it evaluates graph-specific, multi-algorithm workflow planning in a stage-wise manner, rather than focusing solely on individual graph computations.
  • The decomposition into decomposition, algorithm selection, and dependency/parameter resolution enables precise error localization, making it possible to identify which planning decision caused a failure.
  • The execution-level validation is a notable strength: every instance is verified by running a hand-written reference program in topological order, providing stronger assurance than semantic labeling alone.
Critical weaknesses
  • 1,000 synthetic NetworkX-centric problems is a narrow distribution; realism and transfer to real pipelines/larger graphs are untested.
  • The evaluator for Task 1 is itself an LLM, and the edge κ is low (0.489) despite high raw agreement—a real concern for the headline metric.
  • End-to-end evaluation is essentially a GPT-based pipeline on one backend, with only two LLM backends overall; the 48.8% figure is therefore not broadly established.
  • IRA is a post-hoc relaxation, not a method that improves planning. It measures ambiguity rather than solving it.
Questions for authors
  • How were the 143 algorithms and 16 categories chosen, and what fraction of plausible real-world graph workflows fall outside this inventory?
  • Can you show that Task 1 conclusions hold under human evaluation, given the low edge κ for the LLM judge?
  • What do results look like end-to-end on open-weight models and with real (not synthetic) graph-analysis questions?
  • Is there a genuine semantic ground truth beneath the single reference algorithm, and how does IRA handle cases where the "wrong" algorithm is not information-preserving?
3 comments
AuthorsOpenReview ↗

Responses to Reviewer Xv1J(1/3)

W1. Domain-grounded workflow construction and execution

Thank you for your suggestion. We searched relevant public benchmarks and graph data resources. To the best of our knowledge, public benchmarks that jointly provide domain-specific analysis questions, corresponding graph data, and executable multi-stage reference workflows remain limited. We therefore surveyed real-world analytics needs, constructed supplementary problems, and evaluated workflow execution.

  1. Supplementary problem construction. We constructed 100 supplementary problems using AMLSim [1] and TwitterSG [2], with 50 problems each in financial transaction analysis and social network analysis. The AMLSim source graph contains 1,000,000 nodes and 18,175,128 edges representing simulated banking transactions, while the TwitterSG source graph contains 753,944 nodes and 12,848,093 edges. We reviewed domain studies and application cases to identify multi-step analytical needs, formulated questions around analytical objectives, data scope, and expected outputs, and manually checked their consistency with the reference workflows in operations and dependencies.

  2. Execution experiments and results. We executed the reference workflows to obtain ground-truth answers and ran our three-stage pipeline across five model configurations. We then executed the generated workflows and measured workflow accuracy and final-answer accuracy. As shown in Table 1, with IRA, GPT-5.5 achieves 47.00% workflow accuracy and 34.00% final-answer accuracy on the supplementary set, compared with 53.10% and 45.10% on the original synthetic set. These results provide execution evidence in two application domains and show the performance gap between synthetic and domain-grounded problems.

Table 1. Accuracy of our three-stage pipeline on the 1,000 synthetic problems and 100 supplementary domain-grounded problems.

DatasetModelWorkflow Accuracy w/o IRAWorkflow Accuracy w/ IRAFinal-answer Accuracy w/o IRAFinal-answer Accuracy w/ IRA
Synthetic (1,000)Qwen3-8B6.50%7.00%2.60%2.70%
Synthetic (1,000)Qwen3.8-Flash (Non-Thinking)41.90%44.30%35.20%36.80%
Synthetic (1,000)Qwen3.8-Flash (Thinking)47.90%48.10%39.40%39.50%
Synthetic (1,000)DeepSeek-V4-Flash46.90%52.20%39.40%41.80%
Synthetic (1,000)GPT-5.548.80%53.10%42.40%45.10%
Domain-grounded (100)Qwen3-8B4.00%4.00%3.00%3.00%
Domain-grounded (100)Qwen3.8-Flash (Non-Thinking)32.00%34.00%24.00%24.00%
Domain-grounded (100)Qwen3.8-Flash (Thinking)34.00%37.00%26.00%27.00%
Domain-grounded (100)DeepSeek-V4-Flash39.00%42.00%30.00%32.00%
Domain-grounded (100)GPT-5.543.00%47.00%32.00%34.00%

References

  1. Suzumura, T., and Kanezashi, H. "Anti-Money Laundering Datasets: InPlusLab Anti-Money Laundering DataDatasets." 2021. https://github.com/IBM/AMLSim/
  2. Pougué-Biyong, J., Gupta, A., Haghighi, A., and El-Kishky, A. "Learning Stance Embeddings from Signed Social Graphs." Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining (WSDM '23), 177–185, 2023. https://doi.org/10.1145/3539597.3570401
AuthorsOpenReview ↗

Responses to Reviewer Xv1J(2/3)

Q1. Construction and coverage of the algorithm inventory

Thank you for this question. We built the inventory using the NetworkX 3.5 documentation [5] and assessed its task coverage against an external survey and graph benchmarks.

  1. Algorithm selection and classification. We selected independently callable classical graph-analysis entries with defined inputs and outputs. We excluded graph generators, data I/O, format-conversion functions, internal helpers, duplicate aliases, and graph-learning interfaces. We grouped the 143 retained entries by their primary analytical objective into 16 categories, assigning each entry one primary category.

  2. Task coverage. The inventory covers most graph-analysis task families in the sources we examined. Of the task families identified in a 2020 graph-computing survey published in The VLDB Journal [1], 92.3% can be addressed by an inventory entry or a composition of supported operations; general subgraph matching is outside the inventory. The covered families account for 90.5% of task selections in the survey's participant responses and 78.2% of task occurrences in its paper sample. Our inventory covers most graph-analysis task families represented in LDBC Graphalytics [2] and the GAP Benchmark Suite [3,4], such as BFS, PageRank, connected components, and shortest-path analysis.

References for Q1

  1. Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., and Özsu, M. T. "The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing: Extended Survey." The VLDB Journal, 29, 595–618, 2020. https://doi.org/10.1007/s00778-019-00548-x
  2. Iosup, A., Hegeman, T., Ngai, W. L., et al. "LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms." Proceedings of the VLDB Endowment, 9(13), 1317–1328, 2016. https://doi.org/10.14778/3007263.3007270
  3. Beamer, S., Asanović, K., and Patterson, D. "The GAP Benchmark Suite." arXiv:1508.03619, 2017. https://arxiv.org/abs/1508.03619
  4. Azad, A., Aznaveh, M. M., Beamer, S., et al. "Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite." Proceedings of the 2020 IEEE International Symposium on Workload Characterization, 216–227, 2020. https://doi.org/10.1109/IISWC50251.2020.00029
  5. NetworkX Developers. "NetworkX 3.5 Documentation." 2025. https://networkx.org/documentation/networkx-3.5/

W2 / Q2. Human validation of the Task 1 evaluator

Thank you for your suggestion. We further analyzed the same 200 Task 1 predictions used in the earlier human–LLM agreement study, examining both judgment agreement and method rankings to assess the reliability of the LLM judge and the Task 1 comparative conclusions.

  1. The LLM judge maintains high direct agreement with human judgments despite the lower edge-level κ. As shown in Table 2, agreement rates for node, edge, and complete-workflow judgments are 96.0%, 97.0%, and 95.5%, respectively. κ also accounts for the expected agreement associated with the evaluators' label distributions. When both evaluators predominantly assign "correct" labels, expected agreement is already high, so high observed agreement can coexist with a lower κ. The workflow-level κ of 0.876 further supports agreement on overall correctness.

  2. Human evaluation preserves the method ranking, supporting the LLM judge for method comparisons. As shown in Table 3, both evaluations rank the methods as Graph-based, ToT, CoT, and GoT, in that order. Graph-based achieves 86.0% accuracy under human evaluation and remains the best-performing method. These results show that the LLM judge accurately reflects the relative performance of these methods on the audited subset, while the conclusion favoring Graph-based also holds under human evaluation.

Table 2. Agreement between evaluators on the same 200 Task 1 workflow predictions.

MetricHuman–humanLLM–human
Node93.5%96.0%
Edge99.5%97.0%
Workflow93.5%95.5%

Table 3. Overall workflow accuracy under the LLM judge and human evaluation on the same 200 Task 1 predictions.

MethodLLM judgeHuman evaluation
Graph-based84.0%86.0%
ToT76.0%82.0%
CoT74.0%78.0%
GoT62.0%68.0%
Overall74.0%78.5%
AuthorsOpenReview ↗

Responses to Reviewer Xv1J(3/3)

W3 / Q3. End-to-end results across models and application domains

Thank you for your suggestion. We expanded the end-to-end evaluation to five model configurations, including the open-weight Qwen3-8B and the Thinking and Non-Thinking modes of Qwen3.8-Flash. We report both workflow accuracy and final-answer accuracy on the original 1,000 synthetic problems and the 100 supplementary domain-grounded problems described above.

  1. Some non-GPT backends achieve end-to-end results close to those of GPT-5.5. As shown in Table 1 in Response 1/3, without IRA on the synthetic set, DeepSeek-V4-Flash and Qwen3.8-Flash (Thinking) achieve workflow accuracies of 46.90% and 47.90%, respectively, close to GPT-5.5's 48.80%; both achieve 39.40% final-answer accuracy. The open-weight Qwen3-8B achieves 6.50% workflow accuracy and 2.60% final-answer accuracy. These results show that performance close to the originally reported level is also obtained on non-GPT backends, while models still differ substantially in their ability to complete the full analysis workflow.

  2. The supplementary domain-grounded problems are more challenging for most models. As shown in Table 1 in Response 1/3, with IRA, GPT-5.5 achieves 47.00% workflow accuracy and 34.00% final-answer accuracy on the supplementary domain-grounded set, compared with 53.10% and 45.10% on the synthetic set. These results provide evidence from workflow execution on domain-grounded problems and show that translating domain analysis requirements into executable workflows that produce correct answers remains challenging.

W4 / Q4. Semantic Alternatives and End-to-End Execution with IRA

Thank you for your valuable comment. IRA's primary role is to identify potentially executable workflows whose algorithm choices differ from the reference but still satisfy the task's semantic requirements. We then execute these workflows end to end to determine whether they achieve the analytical objective.

  1. End-to-end execution benefit. We executed model-generated workflows on 1,000 synthetic and 100 domain-grounded problems. As shown in Table 1 in Response 1/3, with IRA, GPT-5.5's final-answer accuracy increased from 42.40% to 45.10% on the synthetic set and from 32.00% to 34.00% on the domain-grounded set. These additional correct answers show that IRA-identified alternatives can complete more tasks when executed.

  2. Semantic basis and execution boundary. Predicted workflows must still perform the analytical operations required by the reference workflow. When algorithms share the same core computation but return results in different forms, IRA assesses whether the alternative can provide the information needed downstream under the given graph and parameter conditions. For example, for a reachable node pair in a unit-weight graph, dijkstra_path returns a path whose length can be obtained with len(path) - 1. If a downstream step instead needs the path's nodes, a length alone cannot recover them, so IRA rejects the reverse substitution. Accepted workflows must still execute successfully and produce correct final answers. We continue to encourage models to choose algorithms that directly satisfy the task's semantic requirements and provide the required downstream results, reducing errors from additional conversions.

Reviewer_JPphOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

GPBench evaluates whether language models can turn natural-language graph analysis requests into multi-stage workflows. The benchmark contains 1,000 problems with reference workflows validated by execution and evaluates three steps separately: identifying the operations and their dependencies, selecting an algorithm for each operation, and binding intermediate outputs to downstream parameters. Graph Planner uses graph-specific operation descriptions to guide decomposition, while a hierarchical knowledge base narrows algorithm selection to a task category and helps distinguish similar algorithms. The composed GPT-5.5 pipeline achieves 48.8% under strict reference matching and 53.1% under intermediate-result alignment, which accepts alternative algorithm choices when their outputs satisfy downstream requirements.

Critical strengths
  • The paper gives a concrete formulation of multi-stage graph analysis planning. It separates workflow construction, algorithm selection, and cross-stage parameter binding, then instantiates this formulation in a benchmark of 1,000 problems containing 3,360 operations and five workflow topologies. The reference programs are executed to verify that the annotated workflows describe runnable computations. This provides a useful evaluation resource for a problem that is otherwise difficult to study reproducibly.

  • The evaluation distinguishes local correctness from complete workflow correctness. Overall Accuracy@k requires the reference algorithm to appear in the candidate set for every operation, while Dynamic Dependency Accuracy requires every cross-stage binding in a problem to be correct. This granularity is consequential because it reveals whether a model fails to identify suitable algorithms or fails to compose their inputs and outputs correctly, two failure modes that final-answer accuracy alone cannot separate.

Critical weaknesses
  1. The benchmark does not establish whether a predicted workflow successfully solves the underlying problem. Most evaluation is based on agreement with a single reference workflow, although the same analysis can often be implemented using different algorithms, intermediate representations, or parameterizations. Intermediate-result alignment partially relaxes this criterion through predefined compatibility transformations, but the predicted workflows are still not executed. The evaluation therefore cannot reliably distinguish an invalid plan from a functionally correct alternative, which limits the benchmark’s validity as a measure of practical workflow orchestration.

  2. The need for the proposed multi-stage planning pipeline is not adequately established. A capable model could generate the complete workflow, or executable code, in one pass and revise it using execution feedback. The paper does not compare its pipeline with a same-model one-shot planner or an execution-based agent under comparable inference budgets. Consequently, the experiments show that the individual stages can be evaluated and improved in isolation, but do not show that separating them produces a more accurate or efficient end-to-end system.

Questions for authors
  1. Could the authors clarify whether workflows produced by the complete system were executed on the corresponding graph inputs? If execution was evaluated, reporting runtime success and final-answer correctness would help determine how closely the reference-matching metrics reflect functional correctness. If it was not, how should valid workflows that differ from the reference be treated?

  2. Was the proposed pipeline compared with an agentic harness that generates a workflow or program, executes it, and revises it using execution feedback? Such a comparison seems important because execution and repair may resolve algorithm-selection or parameter-binding errors that remain unrecoverable in the current staged pipeline.

  3. Was the complete pipeline compared with a same-model baseline that generates the workflow or executable program in a single pass? A comparison under a similar inference budget would help establish whether separating decomposition, algorithm selection, and parameter binding improves end-to-end performance.

  4. Could the authors clarify how much planning is required by the benchmark questions themselves? In particular, what proportion describes the intended operations and intermediate subsets explicitly, and what proportion specifies only an analytical goal from which the workflow must be inferred?

  5. How should Overall Accuracy@k be interpreted when each operation has multiple candidate algorithms? Does the metric establish that a mutually compatible selection exists across all stages, or only that each reference algorithm appears somewhere in its respective candidate list?

4 comments
AuthorsOpenReview ↗

Responses to Reviewer JPph(1/2)

W1 / Q1. Do predicted workflows run and produce correct answers?

Thank you for the comment. We found that final-answer accuracy was lower than workflow accuracy for all backends. We generated code for workflows that passed our checks, including alternatives that met IRA's compatibility conditions, and executed the code on the corresponding graph inputs. We used the program outputs to determine whether each answer was correct. As shown in Table 1, with IRA enabled, final-answer accuracy ranged from 2.70% to 45.10%, falling 4.30%–10.40% below the corresponding workflow accuracy. When we inspected the generated code, we found that some errors occurred during the conversion of intermediate results. Once a workflow specifies the algorithms and cross-stage dependencies, the generated code must still convert upstream outputs into the inputs required by downstream algorithms. An error in this conversion can produce an incorrect answer even when the workflow passes all checks.

Table 1. Workflow and final-answer accuracy of our three-stage pipeline on the 1,000 synthetic problems.

ModelWorkflow Accuracy w/o IRAWorkflow Accuracy w/ IRAFinal-answer Accuracy w/o IRAFinal-answer Accuracy w/ IRA
Qwen3-8B6.50%7.00%2.60%2.70%
Qwen3.8-Flash (Non-Thinking)41.90%44.30%35.20%36.80%
Qwen3.8-Flash (Thinking)47.90%48.10%39.40%39.50%
DeepSeek-V4-Flash46.90%52.20%39.40%41.80%
GPT-5.548.80%53.10%42.40%45.10%

W2 / Q2. Comparison with an execution-guided agentic harness

Thank you for this suggestion. Our method achieved higher final-answer accuracy with fewer total tokens in all four backend configurations. We compared it with a Codex-based execution-guided harness, using the same execution model for both methods in each configuration. The harness generates and runs a workflow or program and can revise its algorithm choices and parameter bindings based on execution feedback. As shown in Table 2, our final-answer accuracy was 2.60%–5.40% higher, and our total token use was 2.35%–34.09% lower. Execution feedback can reveal runtime errors. When an operation or dependency fails to meet the analytical requirements, the program can still run successfully and return an incorrect answer. Execution status alone cannot reveal such semantic errors. Our pipeline determines the required operations, algorithms, cross-stage dependencies, and parameter bindings before code generation, helping reduce these errors and the cost of repeatedly inferring and revising these decisions during coding.

Table 2. Final-answer accuracy and reported token use on the GPBench test set.

MethodLLM BackendFinal-answer acc. (%)Total tokensExecution tokens
Execution-Guided HarnessQwen3.8-Flash (Non-Thinking)31.4065,828.9829,278.42
Execution-Guided HarnessQwen3.8-Flash (Thinking)34.50107,365.4423,885.60
Execution-Guided HarnessDeepSeek-V4-Flash39.2092,478.2425,110.71
Execution-Guided HarnessGPT-5.540.7082,838.1618,033.50
OursQwen3.8-Flash (Non-Thinking)36.8064,284.9724,977.96
OursQwen3.8-Flash (Thinking)39.5070,769.3321,936.46
OursDeepSeek-V4-Flash41.8073,831.3717,977.96
OursGPT-5.545.1056,629.3714,513.62
AuthorsOpenReview ↗

Responses to Reviewer JPph(2/2)

W2 / Q3. Comparison with a same-model single-pass baseline

Our method achieves higher final-answer accuracy than Unified-Prompt Generation (UPG) across all backend configurations. We added an end-to-end execution comparison on the 1,000-problem dataset, using the same model for both methods in each configuration and executing predicted workflows on their corresponding graph inputs. UPG performs task decomposition, algorithm selection, and parameter and dependency binding in a single response. Table 3 shows that, with IRA, our final-answer accuracy exceeds UPG by 1.80%–17.80%.

Our pipeline achieves higher accuracy than UPG at all three planning stages. Table 4 shows that, for GPT-5.5, stage accuracy is 1.24%–2.90% higher, and final cumulative accuracy increases from 45.20% to 48.80%. Specifying operations, algorithms, and parameters stage by stage allows subsequent decisions to build on the established plan, helping reduce omitted constraints and binding errors.

Table 3. Comparison between Unified-Prompt Generation (UPG) and our three-stage pipeline on the 1,000-problem dataset.

MethodModelWorkflow Accuracy w/o IRAWorkflow Accuracy w/ IRAReported TokensFinal-answer Accuracy w/o IRAFinal-answer Accuracy w/ IRA
UPGQwen3-8B2.70%2.80%43,156.520.80%0.90%
UPGQwen3.8-Flash (Non-Thinking)27.90%28.00%42,174.2419.00%19.00%
UPGQwen3.8-Flash (Thinking)36.10%36.30%52,525.7926.60%26.70%
UPGDeepSeek-V4-Flash43.60%44.00%56,329.8133.80%34.00%
UPGGPT-5.545.20%45.50%43,417.8035.60%35.70%
OursQwen3-8B6.50%7.00%71,853.412.60%2.70%
OursQwen3.8-Flash (Non-Thinking)41.90%44.30%41,307.0135.20%36.80%
OursQwen3.8-Flash (Thinking)47.90%48.10%48,832.8739.40%39.50%
OursDeepSeek-V4-Flash46.90%52.20%55,853.4139.40%41.80%
OursGPT-5.548.80%53.10%42,115.7542.40%45.10%

Table 4. Stage-wise planning accuracy of GPT-5.5 under exact matching without IRA. Stage accuracy is conditional on all preceding stages passing; cumulative accuracy is measured over all questions. For UPG, the stages are evaluation checks applied to a single generated workflow.

StageUPG Stage Acc.UPG Cumulative Acc.Ours Stage Acc.Ours Cumulative Acc.
Task 1: Decomposition79.80%79.80%82.70%82.70%
Task 2: Algorithm Selection71.43%57.00%72.67%60.10%
Task 3: Parameter and Dependency Resolution79.30%45.20%81.20%48.80%

Q4. How much workflow information is supplied by the questions?

Thank you for raising this question. We manually classified the benchmark questions by the workflow information provided in their wording. Of these questions, 19.5% explicitly specify the analytical operations and intermediate subsets, 2.9% state only an analytical goal, and the remaining 77.6% provide varying degrees of guidance on operations or dependencies through their application descriptions. Even when the operations and intermediate subsets are explicit, the model still needs to choose specific algorithms, parameters, and data representations and determine how to pass results between steps. When a question provides partial cues, the model must make the planning decisions left unspecified. For example, "Identify the nodes that connect different regions of the network, then analyze the core formed by those nodes" specifies the order of the analyses and identifies the nodes selected in the first step as the input to the second. When a question states only an analytical goal, the model must infer the full workflow and the intermediate results needed to achieve that goal.

Q5. The meaning of Overall Accuracy@k

Thank you for your question. Overall Accuracy@k is the proportion of questions for which every analysis step's top-k candidate list includes its reference algorithm. We designate one reference algorithm as the gold answer for each step. We choose it based on what the step needs to compute, the properties of the input graph, the required output, the task constraints, and the algorithm's time complexity. This gives us a consistent, reproducible standard for comparing algorithm selection methods. Once the reference algorithms are selected, we check that each step's output can serve as input to the steps that use it. We then run each complete reference workflow to verify that its algorithms work together to produce the required result.

Reviewer_JPphOpenReview ↗

Response to rebuttal

Thank you for the additional experiments. The same-model comparisons address my concern about the missing baselines. I still have a question about the execution results. The response says that workflows passing the checks were executed, leaving unclear whether a workflow rejected by reference matching could receive credit for a correct answer. This was the main issue behind my first comment, since a valid solution need not follow the reference workflow. I appreciate the work on the revision, but will keep my current rating while this point remains unclear.

AuthorsOpenReview ↗

Response to Reviewer JPph

Thank you for further highlighting this issue. In practice, the impact of these workflows on the models’ overall execution performance is negligible. The IRA mechanism almost entirely prevents valid workflows from being excluded merely because they differ from the reference workflows. To verify this, we executed all workflows that failed the checks, and only 0.37% of them produced the correct answer. After including these correct results, the final answer accuracy under each configuration differed from the original result by at most 0.40%. Therefore, the overall trends across models and our conclusions regarding overall execution performance remain unchanged. Thus, although the issue you identified does exist, our evaluation shows that its practical impact on the overall results is very limited.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.