- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes ProEvolve, a graph-based framework for automatically constructing evolving benchmarks for tool-calling agents, addressing the limitations of existing benchmarks with static environments. By representing schemas, data entities, tools, and their dependencies as a unified graph, ProEvolve enables structured environment evolution through graph transformations and generates corresponding executable task sandboxes via subgraph sampling. Experiments in e-commerce and airline booking evaluate the validity, quality, and diversity of the generated environments and investigate agent behavior under environment evolution.
Critical strengths
-
The idea of dynamically evolving environments through graph transformation is interesting.
-
The proposed three explicitly defined evolution strategies makes the environment evolution controllable.
Critical weaknesses
-
The changing graph and environment seem cannot guarantee the behavioral correctness of the evolved envirionments. The proposed graph formalism primarily captures schema elements and tool dependencies, but does not explicitly model behavioral semantics such as preconditions, postconditions, and state-changing effects. Consequently, structurally valid graph transformations do not necessarily produce functionally correct environments. Moreover, since unit tests and oracle trajectories are derived from the generated specifications, the validation pipeline may fail to detect semantic errors already present in those specifications.
-
Oracle-solvable tasks are not necessarily representative of real-world scenarios. The proposed task generation process relies on subgraph sampling and random walks to construct executable trajectories, but such trajectories do not necessarily correspond to realistic user needs or natural workflows. Although oracle replay verifies task solvability, it does not guarantee that the generated tasks reflect meaningful real-world scenarios, potentially limiting the benchmark's practical relevance.
-
Limited evidence that graph-guided evolution improves downstream benchmark quality. Although ProEvolve achieves higher tool and entity diversity than the free-form baseline, these structural metrics do not necessarily translate into more diverse or challenging benchmark tasks. The paper lacks a direct comparison of the generated tasks and their evaluation utility against the baseline, making it difficult to assess the practical benefits of graph-guided evolution beyond structural diversity.
-
Poor representation. The paper especially experiment section relegates too many important details and empirical findings to the appendix, often leaving only brief descriptions in the main text, which makes the results difficult to follow and interpret. Additionally, the appendix suffers from inconsistent formatting and inefficient use of space. For example, page 26 contains only a short paragraph and a small table, leaving most of the page blank. On page 29, several text overflow beyond the boundaries of boxes.
Questions for authors
-
It seems that the parities tool Jaccard metric unreasonable? The paper reported this metric as 0.976m but all evolved environments share the same seed containing 51 tools (If I don't misunderstood) with about 10.8 new tools added per trajectory on average. If so, how can the jaccard diversity be so high?
-
Figure 4(c–d) shows highly model-dependent results, with trace context providing only marginal improvements and summary context improving some agents while substantially degrading others. The paper seemingly lacks a systematic analysis of these inconsistent effects, when and why prior-version experience helps or harms performance under different environment changes.
Some other concerns listed in weakness part
4 comments
Response to reviewer GJg8 [part 2 of 2]
Q1. Why is Jaccard distance so high despite the shared seed?
The high Jaccard distance reflects low overlap among newly added tools, not among complete tool inventories. We compare the added-tool sets from 50 V0→V1 evolution trajectories, excluding the shared seed tools. For each trajectory pair, Jaccard distance measures the fraction of their combined additions that is not shared. Each trajectory introduces relatively few tools, while the high unique-tool ratio indicates that these additions span many distinct tool names across trajectories. These observations are consistent with little pairwise overlap and hence an average distance close to 1, despite all trajectories starting from the same seed.
We will clarify the added-tool set definition and its relationship to the other diversity metrics in Appendix A.3/Table 7, and align the corresponding labels in the main text.
Q2. When and why does prior-version context help or hurt?
This analysis addresses Q3: “Utility: Do evolved environments induce meaningful agent-behavior differences?” Figure 4(c–d) reveals model-specific patterns: Summary Context improves DeepSeek-V3.2, while Claude-Opus-4.5 makes more tool calls without a corresponding performance gain.
We hypothesize that prior experience helps when its assumptions remain relevant but interferes when they become stale. One observed pattern in Appendix B.6 is missed tool discovery under Summary Context for Opus-4.5, including claims that an available tool is unavailable. We will distinguish this observation from the hypothesis in Section 5.3: the analysis demonstrates diagnostic utility, having a more comprehensive discussion in the revision.
I also share some of the other reviewers’ concerns about the graph representation. Although differ, both question whether the graph adequately captures relevant domain constraints. The construction and interaction distinction is useful, but does not explain how omissions or semantic errors in the construction specification are detected.
About my concern, the response remains insufficiently substantiated. Specification-derived tests establish conformance, while plausibility judgments do not necessarily establish behavioral correctness. A targeted case study would help substantiate.
Response to Reviewer GJg8: Specification errors and a targeted case study
We sincerely thank the reviewer for this helpful suggestion. We agree that conformance to the specification and correctness of the specification are distinct properties, and that a targeted case study is the right way to substantiate the latter.
We therefore complement the specification-derived tests with an intent–edit consistency audit. It compares each generated graph edit with its original evolution intent and preceding graph, without access to implementation code. We then trace the flagged cases through execution.
1. Case study: service-down deprecation
| Stage | Evidence |
|---|---|
| Requirement | Take ExchangeReturnRequest offline; deprecate track_refund, list_user_exchange_return_requests and get_order_return_items. |
| Generated edit | Removes the entity, but keeps the three tools on Order relationships (e.g. Order.order_id → Order.payment_history). Structural validation passes. |
| Audit | Both judges flag the same requirement and name the three tools. |
| Execution | The three calls succeed in the preceding version. In the evolved version, all three raise SystemMaintenanceError, as required. |
| Task generation | Of 10 walks forced to include a deprecated tool, 0 produce a task (9 stop at that call). Of 10 control walks, 8 produce a task. |
The discrepancy is confined to the specification; the implementation behaves as required. Comparing the edit with the requirement identifies it, complementing structural validation and specification-derived tests.
A saturation case shows the same pattern. The shortcut get_order_return_requests is not attached to the direct Order.order_id → ExchangeReturnRequest.request_id relationship in the graph, but the implemented tool matches an independent multi-hop database query on 5/5 orders.
2. Audit of released transitions
Two judges from different model families (Claude Sonnet 4.6 and GPT-6 Astra) audited 30 released transitions, 10 per primitive. Each judge checks primitive-specific requirements: required elements are present, nothing outside the deprecation's scope is removed, and shortcuts connect the intended endpoints. For every violation it cites the requirement and the edit element.
- The judges agree on 28/30 transitions (κ = 0.83).
- Neither judge flags a violation in 21/30.
- Both flag 7/30. In 6 of these they name the same element, and we confirmed all 6 manually:
- 4 deprecations, where removal at the relationship level leaves a deprecated tool annotated, or removes a co-located tool that was not deprecated;
- 2 saturations, where the shortcut is attached to intermediate hops.
- In 5 of the 6, executing the implementation shows it follows the intent.
3. What the judges can detect
On mutations that keep the graph structurally valid but violate the intent:
| Sonnet 4.6 | GPT-6 Astra | |
|---|---|---|
| Tool- and field-level mutations detected | 53/55 | 55/55 |
| Relational mutations detected (foreign key, cardinality, shortcut endpoint) | 13/40 | 18/40 |
| Valid optional-field additions accepted | 9/10 | 9/10 |
| Alternative designs accepted | 20/25 | 20/25 |
The judges are most sensitive to tool- and field-level errors. For relational errors, the audit counts should be read as conservative.
Given the tight timeline, we use LLM audit: two independent judges from different model families, validated on the controlled mutations above, with every jointly flagged case verified manually. In the final version, we will add human audit for those transitions.
4. Task executability
Tasks are sampled from each version's executable tool contracts, and every reference-trajectory state is executed; a task is kept only if all states succeed. In a set of 200 tasks generated by this pipeline, all reference trajectories executed successfully. Sixteen of these tasks belong to versions with deprecated tools, and none calls a deprecated tool.
5. Manuscript changes
We will separate three assessment targets in Sections 4.2 and 5.2:
- Intent–edit consistency of the graph specification;
- Targeted behavioral correctness against explicit references;
- Task executability.
We will also add the audit protocol, the judge assessment and both case studies to Appendix A.2, marked as additional assessments.
Response to reviewer GJg8 [part 1 of 2]
Thank you for the detailed feedback. We address validation, task relevance, downstream utility, and presentation below.
W1. Behavioral correctness and shared-specification errors
ProEvolve assesses functional behavior and semantic alignment separately from graph structural validity. Table 1 distinguishes executable checks from environment-edit judgments:
Thus, specification-derived tests assess implementation conformance; the proposal itself is assessed separately, not validated by those test results. The graph makes the intended changes explicit and inspectable across these stages.
We will make this hierarchy explicit in Sections 4.2 and 5.2 through a construction–evaluation map beside Table 1, identifying each assessment's target, reference, and timing.
W2. Are oracle-solvable tasks meaningful user scenarios?
Workflow coherence is assessed separately from oracle solvability. Table 1 and Appendix A.4, Tables 8–9 evaluate whether tasks form realistic customer journeys with natural progression rather than disconnected actions. In the reported sandbox sample, scenario coherence averages 4.75/4.81 and state-transition feasibility 4.50/4.06 for e-commerce/airline, respectively (1–5 scale).
A new study with 48 ProEvolve-generated tasks and four blinded annotators finds Sonnet-4.5–human agreement of κ = .76 for scenario coherence and .79 for state-transition feasibility, providing a separate check of these judgments.
The benchmark targets controlled diagnostic scenarios, complementing real usage logs and domain-specific evaluations rather than exhaustively reproducing real-world requests (Section 4.2; Appendix C). We will clarify the distinction between executability and workflow coherence beside Table 1 and summarize the new agreement results in Section 5.2, with the protocol in Appendix A.5.
W3. Does graph guidance improve downstream benchmark quality?
Our new task-level comparison shows significantly greater difficulty separation with graph-guided construction than with label-only free-form generation. Graph-path and operation constraints make difficulty targets operational. We evaluate both generators' tasks with GPT-5 under the same agent-evaluation setup.
Entries report GPT-5 state-wise success rates C and their differences. ± denotes 95% CI half-widths; z uses SE = half-width/1.96 on unrounded values. The between-generator difference in easy–hard gaps is .17 ± .13 (z = 2.62, p ≈ .009).
Graph-guided tasks show a monotonic easy-to-hard decline and a larger gap (.28 versus .11), linking explicit difficulty controls to differentiated agent performance beyond structural diversity. We will clarify how typed evolution edits connect to version-grounded task construction in Sections 4.1–4.3 and add this comparison to Section 5.2, with the protocol in the appendix.
W4. Main-text detail and appendix layout
We will move the essential construction and evaluation details into the main text: the graph's cross-stage role in Sections 4.1–4.3, the evaluation hierarchy and key experimental details in Sections 5.1–5.2, and the diagnostic interpretation in Section 5.3.
We will shorten repetitive appendix material, remove the unnecessary page break on page 26, fix the overflowing example box on page 29, and align the validation descriptions and Jaccard labels across the text and tables.